//
// demonstrates an insertion sort
// Written by Maxwell Sayles, 2001, for CPSC331, University of Calgary.
//

#include <stdlib.h>
#include <time.h>

#include <iostream>
using namespace std; 

const int numElements = 128; // number of elements to sort


//
//
// This routine sorts an array of integers in ascending order.
//
// The algorithm is taken from pp. 2-4.
//		Cormen, Thomas H., et al.  Introduction to Algorithms.  
//		The MIT Press, 1990.
//
void InsertionSort (int A[], int elementCount)
{
	for (int j = 1;  j < elementCount;  j = j + 1)
	{
		int key = A[j];
		// insert A[j] into the sorted sequence A[1..j-1]
		int i = j - 1;
		while ((i >= 0) && (A[i] > key))
		{
			A[i+1] = A[i];
			i = i - 1;
		}
		A[i+1] = key;
	}
}


//
// program entry
//
int main()
{
	int i = 0;

	// seed the random number generator
	srand((unsigned int)time(0));

	// create an array of random integers
	int array[numElements];
	for (i = 0;  i < numElements;  i = i + 1)
	{
		array[i] = rand() % numElements; // keep numbers in the range of 0-numElements
	}

	// sort the array
	InsertionSort (array, numElements);

	// print the array
	for (i = 0;  i < numElements;  i = i + 1)
	{
		cout << array[i] << ' ';
	}
	cout << endl;

	return 0;
}