Insertion Sort Demo

The insertion sort is another sorting algorithm. Just like the Bubble Sort, it has a very simple implementation and its easy to be able to see whats going on. While it can be more efficient than the Bubble Sort, it is not recommended to handle sorting large amounts of data (depending on size). For large amounts of data, a Merge Sort, Quick Sort, or the Heap Sort is most appropriate.

The sorting process is as follows:

•  Best case scenario for this algorithm is O(n) where n=1, so only 1 swap is done, Average case and Worst case scenario is O(n^2)
• An example of a worst case scenario is when the collection is in reverse order (like 5,4,3,2,1), a best case scenario is when the collection is already sorted or only 1 swap needs to be done (like 1,2,3,5,4), and average case is where the collection is completely unsorted (like 2,5,1,4,3)

Implementation:

class Program

    {

        static void Main(string[] args)

        {

            Console.WriteLine("Unsorted:");

            int[] collection = { 3, 5, 64, 1, 9, 7, 11, 23, 50 };

            for (int i = 0; i < collection.Length; i++)

            {//first lets write the collection before its sorted

                Console.Write("{0} ", collection[i]);

            }

            Console.WriteLine();

            Console.WriteLine();

           

            //here begins the insertion sort 



            int temp;

            int x;

            for (int i = 0; i < collection.Length; i++)

            {

                temp = collection[i];

                /*temp is equal to the first index of the array, 

                 * so when i = 1, temp will equal the value of whichever 

                 * index the array has for position 1, so if position 1 contains the number 7, temp = 7*/

                x = i - 1;//variable x is equal to i - 1, which will be used in the comparision statement below
 

                /*while x is greater than or equal to 0 AND temp is less than the current index of the array */

                while (x >= 0 && temp < collection[x])
                {

                    collection[x + 1] = collection[x];//make the swap

                    x--;

                    /*move down the collection, we start at position 1 of the array, 

                     * but we subtract until we're at the end of the array (the end position of an array is

                     * written as Length - 1).*/

                }

                collection[x + 1] = temp;//swap completed



               

            }

            Console.WriteLine("Sorted!");

            for (int i = 0; i < collection.Length; i++)//re-write the collection array to the console window

            {

                Console.Write("{0} ", collection[i]);

            } 

            Console.ReadLine();

        }

    }

Illustrations of the algorithm: