Insertion sort
Insertion sort is a simple sorting technique. It is best suited for small data sets, but it does not suitable for large data sets. In this technique, we pick an element and insert it in its appropriate place. Insertion sort is not a fast sorting algorithm because it uses the nested loops to shift the elements in their place. But this is a better sorting technique than bubble sort and selection sort because the complexity of insertion sort is less than both.
If you have n elements in the array, you will need (n-1) pass to sort it.
Complexity table of Insertion sort
| Complexity | Best case | Average case | Worst case |
| Time | O(n) | O(n2) | O(n2) |
| Space | O(1) |
Insertion sort algorithm
Insertion_sort(A)
{
Repeat for i = 2 to the length of A
{
item = A[i]
j = i – 1
Repeat while (j>0 and A[j] > item)
{
A[j+1] = A[j]
j = j – 1
} // end of while loop
A[j+1] = item
} // end of for loop
} // end of the insertion loop
Insertion sort example
Suppose you have the following array, which you have to sort.
| 11 | 8 | 6 | 1 | 9 | 2 |
In insertion sort, the first two elements are compared.
There are 6 elements in this array, so you will need 5 iterations to sort it.
| Iteration 1: Since 8 is smaller than 11, it will change its place among themselves. 8 11 6 1 9 2 Iteration 2: Now, you will compare the next two elements (11 and 6). Since 6 is smaller than 11, it will change its place among themselves. After this, 8 and 6 will compare, 6 is smaller than 8, so it will change its place among themselves. 6 8 11 1 9 2 Iteration 3: Now, you will compare 11 and 1. Since 1 is smaller than 11, it will change its place among themselves. After this, 8 and 1 will compare, 1 is smaller than 8, so it will change its place among themselves. 1 6 8 11 9 2 Iteration 4: Now, you will compare 11 and 9. Since 9 is smaller than 11, it will change its place among themselves. 1 6 8 9 11 2 Iteration 5: Now, you will compare 11 and 2. Since 2 is smaller than 11, it will change its place among themselves. After this, 9 and 2 will compare, 2 is smaller than 9, so it will change its place among themselves. 1 2 6 8 9 11 |
Insertion sort program in C language:
#include<stdio.h>
void main ()
{
int i, j, k, temp;
int a[6] = { 11, 8, 6, 1, 9, 2};
printf("\n Insertion sort \n");
for(k=1; k<6; k++)
{
temp = a[k];
j= k-1;
while(j>=0 && temp <= a[j])
{
a[j+1] = a[j];
j = j-1;
}
a[j+1] = temp;
}
for(i=0;i<6;i++)
{
printf("\n%d\n",a[i]);
}
}
Output
Insertion sort 1 2 6 8 9 11
Insertion sort program in java language:
public class InsertionSort
{
public static void main(String[] args)
{
int[] a = {11, 8, 6, 1, 9, 2};
for(int k=1; k<10; k++)
{
int temp = a[k];
int j= k-1;
while(j>=0 && temp <= a[j])
{
a[j+1] = a[j];
j = j-1;
}
a[j+1] = temp;
}
System.out.println("Insertion sort ");
for(int i=0;i<10;i++)
{
System.out.println(a[i]);
}
}
}
Output
Insertion sort 1 2 6 8 9 11