Write a Program to Insertion Sort in C

Insertion Sort

Insertion sort is a simple sorting algorithm that works like sort a set of playing card in our hands.

as like this,

This is an in-place (Pick and Put on the Appropriate place) comparison-based sorting algorithm. Here, a sub-list is maintained which is always sorted. For example, the lower part of an array is maintained to be sorted. An element which is to be inserted in this sorted sub-list, has to find its appropriate place and then it has to be inserted there. Hence the name, insertion sort.

The array is searched sequentially and unsorted items are moved and inserted into the sorted sub-list (in the same array). This algorithm is not suitable for large data sets as its average and worst case complexity are of Ο(n²), where n is the number of items.

How insertion sort Algorithm works?

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.

Algorithm

Now we have a bigger picture of how this sorting technique works, so we can derive simple steps by which we can achieve insertion sort.

Step 1 − If it is the first element, it is already sorted. return 1;

Step 2 − Pick next element

Step 3 − Compare with all elements in the sorted sub-list

Step 4 − Shift all the elements in the sorted sub-list that is greater than the 

              value to be sorted

Step 5 − Insert the value

Step 6 − Repeat until list is sorted

/*Sorting Elements of an array in ascending order using insertion sort algorithm*/

#include<stdio.h>
#include <conio.h>

void 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]);
}
    getch();
}

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