Sorting Magic – Insertion Sort

Greetings fellow Mages!

Insertion sort has better performance than bubble sort and selection sort in most cases. It would be a very good idea to use insertion sort when the list is almost in order, than using bubble sort or selection sort. You will understand the reason behind this when we go into details on how this magic works.

As usual let’s take an example array.

5    2    1    4    6

We can divide this array into two imaginary portions ; sorted portion and unsorted portion. Since the array is not in any order, currently sorted portion has no elements and unsorted portion has all the elements. Our goal would be to get all the elements into sorted portion and empty out the unsorted portion. To distinguish between sorted and unsorted portions, let’s place an imaginary wall (|) between them.

|  5    2    1    4    6

Now to achieve our goal using the insertion sort method, we need to follow the following steps.

  1. Consider the very first element in the array. Since a single element by itself is already sorted, move the wall inwards.

Therefore, we can move the wall into the array as follows,

5  |  2    1    4    6

Now we have one element inside the sorted portion, let’s move on sorting the others.

  1. Consider the second element and compare it with the last element in the sorted portion.
  2. Since 2 < 5, as we move the wall inwards, in order to make room for 2, we got to move 5 with the wall as well.

Then the array would look like this,

2    5  |  1    4    6

Both wall and the element 5 is moved inwards and element 2 is inserted as it preserves the order in the sorted portion. Moving on,

  1. Consider the third element of the array and compare it with the last element in the sorted portion.
  2. Since 1 < 5, compare it with the other element of the sorted portion.
  3. Since 1 is less than both 5 and 2, as we move the wall inwards, we got to move 5 and 2 with it as well.

This will result in an array like this,

1    2    5  |  4    6

The imaginary wall , element 5 and element 2 have been moved inwards to the array to make room for element 1 to be inserted into its correct place. Following the same procedure,

  1. Consider the fourth element of the array and compare it with the last element of the sorted portion.
  2. Since 4 < 5, compare it with the previous element of the sorted portion.
  3. Since 4 > 2, we can stop comparisons and start moving the wall and element 5 in order to make room for element 4.

Then the resulting array as follows,

1    2    4    5  |  6

Here we only had to move element 5 with the imaginary wall because element 4 is larger than element 1 and element 2. Therefore no need to move element 1 and element 2 to make room for element 4. Just moving element 5 would be sufficient for element 4 to be inserted in its correct place.

Same drill again,

  1. Consider the fifth element (last element) of the array and compare it with the last element of the sorted portion.
  2. Since 6 > 5, we can just move the wall inwards and not worry about moving other elements.

Then the array would look like this,

1    2    4    5    6  |

Congrats! Now you have a sorted array. Now you can see, all the elements have been moved into the sorted portion while unsorted portion has emptied out. This is what we wanted. Let me just erase the imaginary wall and present our ordered array now,

1    2    4    5    6

This is Insertion sort. You start at the beginning of the array and traverse to the end while moving the imaginary wall inwards in each step. The element you consider in each step is inserted at the right place by shifting the other elements with the wall if needed.

Suppose you have a really large array to sort but only a few element are out of order and rest are in the correct order. Then insertion sort would be a better option because it only traverse the array once and only shift element when needed. This results in better performance most of the time.

Analysis of this magic will be covered in a later post. Till then practice this magic and be good at it. Bye!!!

Advertisements

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