Insertion Sort

Insertion sort is very simple sorting algorithm. It is an efficient algorithm to sort small number of elements.

Insertion sort works the way many people sort a hand of playing card.We then remove one card at a time from the table and insert it into the
correct position in the left hand. To find the correct position for a card, we compare
it with each of the cards already in the hand, from right to left, as illustrated in
Figure 2.1. At all times, the cards held in the left hand are sorted, and these cards
were originally the top cards of the pile on the table[1].

In insertion sort we start with the second element of array and insert this element at the correct position into the sorted subarray to the left of that element. We take next elements and insert this element at the correct position into the left sorted subarray. We continue in this manner until whole array is sorted(we reached at the end of array). We insert any element into left sorted array, at correct position by comparing the element by the elements of left sorted subarrray.

Now, i will show the procedure of Insertion Sort with the help of diagram and then i will make a C function to perform insertion sort on the array of integer.

Suppose we have an array of six elements A[ ] = { 5,2,4,6,1,3 }

 

This diagram shows the execution of insertion sort on a typical array. This diagram is self explanatory. On the first iteration second element 2 is compaired with first element 5, as 5 is the only element in the left sorted subarray(array with only one element is sorted in itself). Since 5 is greater than 2 hence 5 is shifted toward one place right and 2 is placed before 5(previous place occupied by element 5). Now after first iteration there are two elements on left sorted subarray. Now the 3rd element 4 is placed at the proper position into the left sorted subarray. The whole sorting algorithm continue in this fashion untill no element is left in right unordered array(see figure). When we shift more than one element during the execution , we shift the element toward right in the order of decreasing index value i.e. the element with the highest index value(in left sorted subarray) is shifted first then element with next lower index and so on. The order of shifting is shown in the figure with the help of thickness of arrow. The element with the thinest arrow is shifted first then next element with relativaly high thickness and so on.

Now I implement Insertion Sort in C language.


/* Insertion Sort Function
Created by: Abhinav Kushwaha*/

void InsertionSort(int *num, int length){
    int i=0,j=0,key;
    for(i=1;i<length;i++){
        key=num[i];    //store the key value so that we can place it at proper position
        j=i-1;            //the upper bound of left sorted array will be i-1
        while((j>=0)&&(key<num[j])){
            num[j+1]=num[j];    //shift the elements of sorted left subarray toward one place right
            j–;
        }
        num[j+1]=key;    //after shifting the elements we place the key element at proper position
    }
}

This function takes Array and its Length as parameter and perform insertion sort on that array. Since array is passed by reference the change in array in this function is also reflected in calling function.The outer for loop covers the right unordered subarray and inner while loop covers the left sorted subarray. key is variable that holds the element value which is currently under consideration(element in shaded box in the diagram). j variable span over left sorted subarray. In while loop we check where we have to insert the ‘key’ variable(the element under process).

while((j>=0)&&(key<num[j])){
    num[j+1]=num[j];
    j–;
}

The condition((j>=0) ) in while loop checks if the lower bound of array is reached or not. The condition((key<num[j])) in while loop ensure that comparision is made until procesing element(key) is less that the comparing element is left subarray.

The statement ( num[j+1]=num[j]; ) shifts the elements of left subarray to right, to make room for insertion of key element. After shifting of elements of left subarray thw while loop terminates , now statement ( num[j+1]=key; ) insert(store) the key element at the proper position.