Insertion Sort

The main idea of insertion sort is

• Start by considering the first two elements of the array data. If found out of order, swap them

• Consider the third element; insert it into the proper position among the first three elements.

• Consider the fourth element; insert it into the proper position among the first four elements.

• … …

This algorithm is not something uncommon to the persons who know card playing. In the game of cards, a player gets 13 cards. He keeps them in the sorted order in his hand for his ease. A player looks at the first two cards, sorts them and keeps the smaller card first and then the second. Suppose that two cards were 9 and 8, the player swap them and keep 8 before 9. Now he takes the third card. Suppose, it is 10, then it is in its position. If this card is of number 2, the player will pick it up and put it on the start of the cards. Then he looks at the fourth card and inserts it in the first three cards (that he has sorted) at a proper place. He repeats the same process with all the cards and finally gets the cards in a sorted order. Thus in this algorithm, we keep the left part of the array sorted and take element from the right and insert it in the left part at its proper place. Due to this process of insertion, it is called insertion sorting.

Let’s consider the array that we have used in the selection sort and sort it now with the insertion sorting. The following figure shows the insertion sort of the array pictorially.

The array consists of the elements 19, 12, 5 and 7. We take the first two numbers i.e. 19 and 12. As we see 12 is less than 19, so we swap their positions. Thus 12 comes at index 0 and 19 goes to index 1. Now we pick the third number i.e. 5. We have to find the position of this number by comparing it with the two already sorted numbers. These numbers are 12 and 19. We see that 5 is smaller than these two. So it should come before these two numbers. Thus the proper position of 5 is index 0. To insert it at index 0, we shift the numbers 12 and 19 before inserting 5 at index 0. Thus 5 has come at its position. Now we pick the number 7 and find its position between 5 and 12. To insert 7 after 5 and before 12, we have to shift the numbers 12 and 19 to the right. After this shifting, we put number 7 at its position. Now the whole array has been sorted so the process stops here.

Following is the code of the insertion sort in C++.

void insertionSort(int *arr, int N) { int pos, count, val; for(count=1; count < N; count++) { val = arr[count]; for(pos=count-1; pos >= 0; pos--) if (arr[pos] > val) arr[pos+1]=arr[pos]; else break; arr[pos+1] = val; } }

In this sorting function, we start the process from index 0 and 1 and swap them. Afterwards, we go to the third position and put it into its proper position. While inserting a number in the sorted portion of the array, we have to shift the elements. This shifting is an additional overhead of this sorting algorithm. Due to this shifting, the sorting requires more time. This algorithm is also an in place algorithm as we don’t need any additional storage. At the most, we need some variables of local nature, normally used in programs.

From the above code, we see that the name of this sorting routine is insertionSort. It takes an array and its size as arguments. There are local variables pos, count and val declared in this function. After this there is a for loop that starts from the count having value equal to 1. Now we put the value of count index (i.e. arr[count]) in variable val. This value has to find its place in the left sorted portion of the array. To find that position we have to execute one more for loop. This loop starts from count-1 and goes to down to zero. In the body of the loop we compare the value of val with the value at current position in the array i.e. arr[pos]. If val is less than the arr[pos] i.e. value at current index. It means that the val has to go to the left position of arr[pos].So we shift the arr[pos] to right to create place for the new value i.e. val. When the loop exits, we put this value val at arr[pos + 1]. Thus we have inserted the number in the array at its proper position.

Following is the step by step explanation for the insertion sort of the above example with same previous array.

First of all we take the first two elements 19 and 12. As 12 is less than 19, we do right shift on 19. And put 12 at its position i.e. index 0. Afterwards, we go to index 2. There is 5 at this position. As we see that 5 is less than the other elements on the left side of array, it has to come at the first position. To bring 5 to first position, the number 12 and 19 has to be shifted to right. After this shifting, the position of index 0 becomes empty and we put 5 there. Finally, there is number 7. The position of 7 will be between 5 and 12. For this, we have to shift 12 and 19 towards right so that the place for 7 could be created. We put 7 at that place. Thus the array is sorted now.

Insertion Sort Analysis

Let’s analyze that when the value of N increases. How much time for insertion sort increases? In the code of insertion sort, we have seen that there are outer and inner loops. Due to these two loops, we can understand that it is also like N² algorithm. In the sort process, there may be a situation that every iteration inserts an element at the start of the array by shifting all sorted elements along. Now if we have to bring the second element to its position, there will be need of shifting the first element. This means that we have to shift one element. Similarly, for placing the third element at the start position (we are discussing the worst case scenario in which at every iteration the element has to go to the first position), we have to shift two elements. Thus we sum up all the shiftings, the total becomes 2 + 3 + 4 +……. + N-1 + N.

The summation can be written as follows.

Total = (2 + N ) (N -1) / 2

= O (N²)

From this expression, we see that when the value of N increases, the value of N² will dominate. It will increase significantly with respect to N. Thus we see that insertion sort is also an N² algorithm like selection sort.

Technorati Tags: insertion sort algorithm,insertion sort,algo and ds,data structure and algorithm tutorial