// Insert.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<iostream.h>

//this is array size
#define SIZE 15

int main()
{
//this is the array we want to sort
	int array[]={23,22,10,3,9,2,1,5,6,0,34,44,55,22,11};
//function declaration
	void InsertionSort(int * ,int);
//we call the function to sort array:

	InsertionSort(array,SIZE);

//these lines just prints all values in array after sorting:
	int i=0;
	for(i=0;i<SIZE;i++) cout << array[i] << '\n';
	
	return 0;
}



//function insertionsort takes array pointer and its size
void InsertionSort(int * a,int size)
{
	int select,i,j,k;

//traverse the whole array.Start from 2nd element
	for(i=1;i<SIZE;i++)
	{
//This loop is from first element to the ith element.
		for(j=0;j<i;j++)
		{
//if ith element is < jth element then we must 
//place ith element in its proper location.
//To do this we: 
//  1) store ith in variable 'select' 
//  2) shift all elements from jth to j+1 until we reach ith
//	3) put select in the jth location.

			if (a[i]<a[j])
			{
				select=a[i];
				for(k=i-1;k>=j;k--)	a[k+1]=a[k];
				a[j]=select;
			}
		}
	}
}