Insertion Sort Algorithm

This tutorial is intended to provide you information about what insertion sort algorithm is and how to implement it in programming rather than it's technical stuff, properties and comparision with other sorting algorithm. If you know what insertion sort algorithm is then, visit this page to learn about properties of insertion sort and comparision with other sorting algorithm.

How insertion sort Algorithm works?

Working of Insertion sort algorithm in programming to sort elements of an array.

Explanation

Suppose, you want to sort elements in ascending as in above figure. Then,

  1. Step 1: The second element of an array is compared with the elements that appears before it (only first element in this case). If the second element is smaller than first element, second element is inserted in the position of first element. After first step, first two elements of an array will be sorted.
  2. Step 2: The third element of an array is compared with the elements that appears before it (first and second element). If third element is smaller than first element, it is inserted in the position of first element. If third element is larger than first element but, smaller than second element, it is inserted in the position of second element. If third element is larger than both the elements, it is kept in the position as it is. After second step, first three elements of an array will be sorted.
  3. Step 3: Similary, the fourth element of an array is compared with the elements that appears before it (first, second and third element) and the same procedure is applied and that element is inserted in the proper position. After third step, first four elements of an array will be sorted.

If there are n elements to be sorted. Then, this procedure is repeated n-1 times to get sorted list of array.

C Program Sort Elements Using Insertion Sort Algorithm


/*Sorting Elements of an array in ascending order using insertion sort algorithm*/
#include<stdio.h>
int main()
{
	int data[100],n,temp,i,j;
	printf("Enter number of terms(should be less than 100): ");
	scanf("%d",&n);
	printf("Enter elements: ");
	for(i=0;i<n;i++)
	{
		scanf("%d",&data[i]);
	}
	for(i=1;i<n;i++)
	{
		temp = data[i];
		j=i-1;
		while(temp<data[j] && j>=0)
/*To sort elements in descending order, change temp<data[j] to temp>data[j] in above line.*/
		{
			data[j+1] = data[j];
			--j;
		}
		data[j+1]=temp;
	}
	printf("In ascending order: ");
	for(i=0; i<n; i++)
		printf("%d\t",data[i]);
    return 0;
}

Note: Though this program is in C, insertion sort algorithm can be similarly used in other programming language as well.

Output

Enter number of terms(should be less than 100): 5
Enter elements: 12
1
2
5
3
In ascending order: 1     2     3     5     12

Here is another source code that uses the same insertion sort algorithm technique to sort elements of an array.

 
/*This source code is also the implemention of  insertion sort algorithm to sort elements of array.*/
/*This program is little complex because it contains multiple loops.*/
/*Program to Sort array in descending order*/
#include <stdio.h>
int main()
{
    int data[100],n,i,j,hold,k;
    printf("Enter number of terms(should be less than 100): ");
    scanf("%d",&n);
    printf("Enter elements: ");
    for(i=0;i<=n-1;++i)
    {
       scanf("%d",&data[i]);
    }
    for(i=1;i<=n-1;++i)
    {
    for(j=0;j<i;++j)
       if(data[j]<data[i])
/*To sort elements in ascending order change < to > in above line.*/
       {
           hold=data[i];
           k=i;
           while(k!=j)
           {
               data[k]=data[k-1];
               --k;
           }
           data[j]=hold;
       }
    }
    printf("In descending Order: ");
    for(i=0;i<=n-1;++i)
     {
       printf("%d    ",data[i]);
    }
    return 0;
}