INSERTION SORT

INSERTION SORT:

In this sorting technique, as the name suggests, insert each element to its proper location. It is simple to implement and efficent on small data set. It is stable, in-place(only requires const amount of extra memory space O(1)) and an online algorithm(i.e. it can sort a list as it recieves).

Worst case:О(n2)

Average Case:О(n2)

Best case:Ω(n)

ALGORITHM:

• Input Array as a[]
• for i = 1 to n – 1
  j = i
  while j > 0 and a[j-1] > a[j]
  swap a[j] and a[j-1]
  j = j – 1
  end while
  end for loop
• PRINT sorted array as a[]

e.g. sort 6,4 2,5

6 , 4 , 2 , 5          4 to be inserted
? , 6 , 2 , 5          j=0, reached boundary
4 , 6 , 2 , 5          4 inserted

4 , 6 , 2 , 5          2 to be inserted
4 , ? , 6 , 5          4>2 shift
? , 4 , 6 , 5          j=0, reached boundary
2 , 4 , 6 , 5          2 inserted

2 , 4 , 6 , 5          5 to be inserted
2 , 4 , ? , 6          6>5 shift
2 , 4 , 5 , 6          4<5, 5 inserted

C SOURCE CODE:

#include<stdio.h>
#include<conio.h>   
void main() 
{ 
int a[100], n, i, j, temp;   
printf("Enter number of elements\n"); scanf("%d", &n);   
printf("Enter %d elements\n", n);   

for (i = 0;i<n; i++)
scanf("%d", &a[i]);

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;
}

printf("Sorted array\n");   
for (i=0;i<n;i++ ) 
printf("%d\t",a[i]);   
getch(); 
}