/*
 * To implement the Insertion Sort algorithm for sorting an array of 8 integers 
 * @author-Karan Narain(karan@iitk.ac.in)
 *
*/

#include <stdio.h>

void insertionSort(int A[])
{
	int i,j,k;
	for(j=1;j<8;j++)
	{
		printf("\n Before Pass %d: ",j);
		for(i=0;i<8;i++)
		{
			printf(" %d ",A[i]);
		}
		printf("\n");
	
		k=A[j];
		//Find appropriate position for insertion of k=A[j] in the sorted sublist
		for(i=j-1; i>=0 && k<A[i] ;i--)
		A[i+1]=A[i];
		//Insert k
		A[i+1]=k;
	}
	printf("\n Sorted list,at the end of Pass %d, is : \n",j-1);
	for(i=0;i<8;i++)
	printf(" %d ",A[i]);
	printf("\n");
}
int main()
{
	int A[8],i;
	printf("\n Enter the 8 array elements : \n");
	for(i=0;i<8;i++)
	{
		scanf(" %d",&A[i]);
	}
	insertionSort(A);
	return 0;
}