Insertion sort is similar to arranging the documents of a bunch of students in order of their ascending roll number. Starting from the second element, we compare it with the first element and swap it if it is not in order. Similarly, we take the third element in the next iteration and place it at the right place in the subarray of the first and second elements (as the subarray containing the first and second elements is already sorted). We repeat this step with the fourth element of the array in the next iteration and place it at the right position in the subarray containing the first, second and the third elements. We repeat this process until our array gets sorted. So, the steps to be followed are:
- Compare the current element in the iteration (say A) with the previous adjacent element to it. If it is in order then continue the iteration else, go to step 2.
- Swap the two elements (the current element in the iteration (A) and the previous adjacent element to it).
- Compare A with its new previous adjacent element. If they are not in order then proceed to step 4.
- Swap if they are not in order and repeat steps 3 and 4.
- Continue the iteration.
The diagram given below will make you understand this better.
Working of insertion sort
Initial array
16 | 19 | 11 | 15 | 10 |
First iteration
16 | 19 | 11 | 15 | 10 |
No swapping –
16 | 19 | 11 | 15 | 10 |
Second iteration
16 | 19 | 11 | 15 | 10 |
Swap
16 | 11 | 19 | 15 | 10 |
Swap
11 | 16 | 19 | 15 | 10 |
Third iteration
11 | 16 | 19 | 15 | 10 |
Swap
11 | 16 | 15 | 19 | 10 |
Swap
11 | 15 | 16 | 19 | 10 |
No swapping –
11 | 15 | 16 | 19 | 10 |
Fourth iteration
11 | 15 | 16 | 19 | 10 |
Swap
11 | 15 | 16 | 10 | 19 |
Swap
11 | 15 | 10 | 16 | 19 |
Swap
11 | 10 | 15 | 16 | 19 |
Swap
10 | 11 | 15 | 16 | 19 |
C code for insertion sort
#include <stdio.h>
#include <math.h>
int main()
{
int a[] = {16, 19, 11, 15, 10, 12, 14};
int i,j;
for(i=0;i<7;i++)
{
j = i;
//i is not the first element
while(j>0)
{
//not in order
if(a[j-1] > a[j])
{
//swapping
int temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
}
//in order
else
{
break;
}
j--;
}
}
for(i=0;i<7;i++)
printf("%d\n",a[i]);
return 0;
}
Explanation of the code
for
(i=0;i<7;i++)
– We are iterating over the array ‘a’.
while (j>0)
– Index of the current element is positive. This means that the element at the index of ‘j’ is not the first element and we need to compare the values.
if (a[j-1] > a[j])
– These two elements are not in order. We need to swap them. else
– The elements are in order, we can break the while loop.
int temp = a[j-1]; a[j-1] = a[j]; a[j] = temp;
– Swapping.