Insertion Sort Demo (C++, C#)


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. It is not recommended to handle sorting large amounts of data (depending on size). For large amounts of data, a Merge Sort, QuickSort, 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)

In pseudo-code:

INSERTION-SORT (A)
1  for i <- 0 to length[A]
2       do nextItem <- A[i]
3        i <- j
4        while j > 0 and A[j - 1] > nextItem
5           do A[j] <- A[j - 1]
6              j <- j - 1
7        A[j] <- nextItem

Implementation C++:

void InsertionSort(vector<int> items, int start, int end)
{
	int nextItem;
	for(unsigned int x = start; x < end; x++)
	{
		nextItem = items[x];
		int j = x;
		while(j > 0 && items[j - 1] > nextItem)
		{
			items[j] = items[j - 1];
			j--;
		}
		items[j] = nextItem;
	}
}

Implementation C#:

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 &lt; 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 comparison 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:

Advertisements

2 thoughts on “Insertion Sort Demo (C++, C#)

  1. Pingback: Quicksort | Bits and Pieces of Code

  2. Pingback: Heapsort C# Tutorial | Bits and Pieces of Code

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s