Algorithm of Insertion Sort

Written by Kousik : 

This is another efficient way of solving a problem related with sorting. This algorithm works as the way people play cards. We present our procedure for insertion sort by the name INSERTION. This function takes an array of n element as input which is to be sorted. This algorithm sorts given n elements by inserting them into their right position.

Procedure INSERTION

{

  For i=1 to n-1 do

  Insert(i);

 

}

Insert(i)/* assumes a[0], a[1],…,a[i-1] are sorted*/

{                  /* Insert a[i] in appropriate position so that a[0],a[1],…a[i-1],a[i] become sorted*/

}

Time complexity of this algorithm:

Look carefully in the algorithm you will see that the algorithm works for each element in the array by keeping a particular element into its right position. So the time complexity will be

                                T(n) =

                                     =n(n+1)/2

                                        <=n²/2=O(n²)

So it is efficient algorithm because it takes the polynomial time complexity for executing.

Now we have to write the C code for this algorithm

/* A c program for insertion sort*/

#include<stdio.h>

#include<stdlib.h>

int *a,n;

void insert();

int main()

{

  int i;

  printf("Enter the total number of elements: ");

  scanf("%d",&n);

  a=(int *)calloc(n,sizeof(int));

  printf("Enter the values: ");

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

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

  insert();

  printf("The sorted array: ");

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

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

  return 0; 

}

void insert(void)

{

    int i,j,temp;

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

                {

                  temp=a[i];

                  j=i-1;

                  while((temp<a[j])&&(j>=0))

                  {

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

                  j=j-1;

                  }

                  a[j+1]=temp;

                }

}