Insertion sort
Suppose an array ‘A’ with ‘n’ elements A[0]. A910,A[20],---------A[N-1] is in memory. The insertion sort algorithm in data structures scans ‘A; from A[0] to A[N-1] insert each element A[k] into its proper position in the previously sorted sub array A[0],A[1],A[2]----
A[K] That is
pass1 A[0] by itself ip trivially sorted.
pass2 A[1] is inserted either before or after aA[0]
So that : A[0],A[1] is sorted
pass3: A[2] is inserted into its proper place in
A[1] A[2], that is before A[0] between A[0]
A[1] or after A[1], so that : A[0],A[1],A[2] is sorted
pass4: [3] is inserted into its proper place in A[1],A[2] so that : A[0],A[1],A[2],A[3] is sorted.
PassN : A[N] is inserted into its proper place in A[1],A[2],-------A[N-1] so that : A[0],A[1]--- is sorted.
Example :
Insertion Sort Program
Implementation of insertion sort in data structures
# include <stdio.h>
# include <conio.h>
void main()
{
int n,i,j,a[20],temp;
void insertion sort(int a[10],int n);
clrscr();
printf(“Enter n value: ”);
scanf(“%d”,&n);
printf(“Enter the elements:\n”);
for(i=0; i<n;i++)
{
scanf(“%d”,&a[i]);
}
Insertion sort(a,n);
}
insertion sort(a,n);
printf(“The sorted elements are:\n”);
for(i=0;i<n;i++)
{
printf(“%5d”,a[i]);
}
}
void insertion sort (int a[20], int n)
{
int i,j,temp;
for(i=1;i<n;i++)
{
if(a[j]<a[j-1])
{
temp=a[j];
a[j]=a[j-1];
a[j-1]=temp;
}
}
}
}
output :
Enter ‘n’ value : 5
Enter the elements: 2 4 3 1 5
The elements are : 2 3 4 5
Time complexity :
Algorithm | Worst case | Average case |
Insertion sort | n(n+1)/2=o(n2) | n(n-1)/4=o(n2) |