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.
(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)
(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)
As you can see from the figures above the insertion sort is very simple. Lets now try it out in C#
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