Insertion sort

Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort, but it has various advantages:

Simple to implement

Efficient on (quite) small data sets

#include<stdio.h>//header file
#include<conio.h>//header file
void main()
{
int arr[100],i,prev,temp,tot;
clrscr();
do //do while looping
{
printf("\nEnter total no.");
scanf("%d",&tot);
}
while(tot>100);
arr[0]=-9999;
for(i=1;i<=tot;i++)
{
printf("Enter the elements");
scanf("%d",&arr[i]);
}
clrscr();
printf("\nThe original array");
for(i=1;i<=tot;i++)
{
printf("%d",arr[i]);
printf("\n");
for(i=2;i<=tot;i++)
{
temp=arr[i];
prev=i-1;
while(temp<arr[prev])
{
arr[prev+1]=arr[prev];
prev--;
}
arr[prev+1]=temp;
}
printf("The sorted array");
for(i=1;i<=tot;i++)
printf("\n%d",arr[i]);
printf("\n");
getch();
}
}