Insertion Sort: One of the simplest sorting algorithms is the insertion sort. Insertion sort consists of n - 1 passes. For pass p = 2 through n, insertion sort ensures that the elements in positions 1 through p are in sorted order. Insertion sort makes use of the fact those elements in positions 1 through p - 1 are already known to be in sorted order. To insert a record, we must find the proper place where insertion is to be made.
A C program to sort integers using insertion sort is given below:
printf("how many numbers u want to enter :\n");
scanf("%d",&n); printf("\nenter the numbers :\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=1;i<n;i++)
{
int val=a[i];
for(j=i-1;j>=0&&val<a[j];j--)
a[j+1]=a[j];
a[j+1]=val;
printf("sorted elements :\n");
for(i=0;i<n;i++)
printf("%d\t",a[i]);
printf("\n");
getch();
}