Insertion Sort
Sorts a set of records by comparing the next record with all the previous elements. Compare next element with previous. If next element is smaller than previous element, then swap both the elements. i.e.
if(arr[j]>arr[i])
swap(arr[j],arr[i);
Example:
The loop may be written as follows:
for I = 2 to n
for j = I-1 to >=1
if(arr[I] < arr[j])
swap(arr[i],arr[j]);
Insertion sort is considered best if most of the data is in sorted order.
Efficiency:
I j number of times
2 1 to 1 1
3 2 to 1 2
4 3 to 1 3
– —— –
– —— –
– —— –
(n-1) (n-2) to 1 (n-2)
n (n-1) to 1 (n-1)
Sum of terms: 1+2+3+…………..+(n-2)+(n-1)
=(n-1)(n-1+1)/2
=n(n-1)/2
=n2/2-n/2
=0.5n2-0.5n
=O(n2)
Note:
An insertion sort may be viewed as a general selection sort in which the priority queue is implemented as an ordered array. We have to only insert elements in priority queue. Once the elements have been inserted, they are already sorted, so that no selection is necessary.
Shell sort is an improvised form of insertion sort, as for k=1, most of the data which is processed is already sorted.
Insertion Sort Program:
#include <stdio.h>
#include <conio.h>
#define MAX 10
void main()
{
int arr[MAX];
int i,j,temp,num,ct;
clrscr();
for(i=0;i<MAX;i++)
{printf(“Enter array elements?”);
scanf(“%d”,&arr[i]);
}
for(i=1;i<MAX;i++)
{
num=arr[i];
ct=i;
for(j=i-1;j>=0;j–)
{if(num<arr[j])
{
temp=arr[ct];
arr[ct]=arr[j];
arr[j]=temp;
ct=j;
}
}
}
printf(“Sorted array using insertion sort is:\n”);
for(i=0;i<MAX;i++)
printf(“%d\t”,arr[i]);
getch();
}