Insertion Sort

Insertion sort is one of the many algorithms that we will cover in this blog. I choose this algorithm to start with because I think that this is a fairly easy to understand (better start with an easy one :) )

To understand the insertion sort imagine that you have a deck of cards that is not sorted. You put this deck of cards on the table and start picking a card one by one; each time putting the card in your left hand. Each time you pick a card you must compare that card with the previous cards until you find a card that is greater than the one you have. By doing so you just sorted the deck of cards on your left hand.

Insertion sort is quite similar. Basically you have a list and you start looping linearly through that list, each time checking with the previous items if the selected item (the key) is smaller than the items before it. If so move that item forward. If the previous item is smaller then you stop checking.

The below figures should make this more clear. (I will refer to the item being sorted as the key.

insertion1 (FIG 1) Start from the element “2”. Check it with the previous element “5”. Since “5” > “2”, move “5” forward (Result shown in Fig 2).

insertion2 (FIG 2) Select the next element “4”. Check it with the previous element “5”. Since “5” > “4”, move “5” forward. Check “4” with “2”. Since “2” < “4” then “2” should not move and thus we stop checking with previous values. Move “4” to the proper index (Result shown in Fig 3)

insertion3 (FIG 3)Select the next element “6”. Check it with the previous element “5”. Since “5” < “6”, “5” should not move and thus we stop checking with previous values (Result shown in Fig 4)

insertion3 (FIG 4)Select the next element “1”. Check it with the previous element “6”. Since 6 > 1 move 6 forward. Check the key(“1″) with the other item “5” since “5” > “1”, move “5” forward. continue the same process with all other elements (Result shown in Fig 5)

insertion4 (FIG 5)

As you can see from the figures above the insertion sort is very simple. Lets now try it out in C#

   1: //unsorted array
   2: int[] list = new int[] { 5, 2, 4, 6, 1 };
   3:
   4: // the key element being sorted
   5: int key;
   6:
   7: //start looping starting from the second element
   8: for (int i = 1; i < list.Length; i++)
   9: {
  10:     key = list[i];//store the key
  11:     int j = i - 1;//get the previous index
  12:
  13:     //loop until you meet a smaller number or 0
  14:     while (j >= 0 && list[j] > key)
  15:     {
  16:         //move the greater number forward
  17:         list[j + 1] = list[j];
  18:         //decrement the counter so that we get the previous element
  19:         j--;
  20:     }
  21:     //set the key in the proper index
  22:     list[j + 1] = key;
  23: }

Conclusion

The insertion sort is a fairly efficient algorithm for sorting small arrays. As you could see in the above explanation you must compare the key with all other elements that are in front of the key (This could suffer performance with large arrays)

The best case scenario for this algorithm would be if the elements in the array are already sorted. This would give us the best performance because there would be no need to compare the key with all the other element in front of it.

The worse case scenario would be if the array is in reverse order. This would force us check each element every time.

I hope I gave a good explanation of this algorithm. Feel free to leave comments/suggestions….

P.S This is my first algorithms article so please be kind; I promise I’ll try to improve :D

kick it on DotNetKicks.com

About these ads

4 Responses to Insertion Sort

  1. Reuben Bartolo says:

    Nice. Was appropriate that the first blog insertion would be about the insertion sort. The figures are a nice touch. Will definitely check this blog out again.

  2. Raffaele Bianco says:

    Hi Marlon,

    I think this blog is a great idea, keep it up.

    A comment on the algo: probably the use of a linked list would help explaining better how insertion sort works.

    Well done master!

  3. Good work!!!

    ————————————-

    http://simply-url.blogspot.com

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

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: