//program to sort an array using insertion sort
#include<iostream.h>
#include<conio.h>
void insertion_sort(int A[20],int N);
void main()
{ clrscr();
  int a[20],n,i;
  cout<<"\n Enter the number of elements:";
  cin>>n;
  cout<<"\n Enter the elements of array:";
  for(i=0;i<n;i++)
  { cout<<"\n Enter a["<<i<<"]:";
cin>>a[i];
  }
  cout<<"\n Array is:";
  for(i=0;i<n;i++)
  cout<<a[i]<<"\t";
  insertion_sort(a,n);
  cout<<"\n Sorted array is:";
  for(i=0;i<n;i++)
  cout<<a[i]<<"\t";
  getch();
}
void insertion_sort(int A[20],int N)
{ int i,j,temp,p;
  for(i=1;i<N;i++)
  { temp=A[i];
j=i-1;
while(A[j]>temp&&j>=0)
{ A[j+1]=A[j];
j--;
}
A[j+1]=temp;
cout<<"\n Array after itteration "<<i<<" is:";
for(p=0;p<N;p++)
cout<<A[p]<<"\t";
  }
}