Insertion sort

Write a program to explain insertion sort. Which type of technique does it belong.

Both the selection and bubble sorts exchange elements. But insertion sort does not exchange elements. In insertion sort the element is inserted at an appropriate place similar to card insertion. Here the list is divided into two parts sorted and unsorted sub-lists. In each pass, the first element of unsorted sub list is picked up and moved into the sorted sub list by inserting it in suitable position. Suppose we have ‘n’ elements, we need n-1 passes to sort the elements.

Implementation of insertion sort in C language:

#include<stdio.h>

int main( )

{

int a[10],i,j,k,n;

printf("How many elements you want to sort?\n");

scanf("%d",&n);

printf("\nEnter the Elements into an array:\n");

for (i=0;i<n;i++)

{

printf("a[%d] = ",i);

scanf("%d",&a[i]);

printf("\n");

}

for(i=1;i<n;i++)

{

k=a[i];

for(j= i-1; j>=0 && k<a[j]; j--)

a[j+1]=a[j];

a[j+1]=k;

} printf("\nElements after sorting: \n");

for(i=0;i<n;i++)

printf("%d\n", a[i]);

return 0;

}

The program output is tested on www.jdoodle.com

Output:

How many elements you want to sort?

6

Enter the Elements into an array:

a[0] = 2

a[1] = 4

a[2] = 6

a[3] = 8

a[4] = 7

a[5] = 5

Elements after sorting: 

   2   4   5   6   7   8

Thanks

Mukesh Rajput