//
//	p.617 Insertion sort
//
//	For nearly sorted data, O(NlogN); for general, O(N^2)
//	Selection - ALL O(N^2)

#include <iostream>
using namespace std;

// prototypes
void Swap(int&, int&);
void InsertIntem(int[], int,  int);
void InsertionSort(int[], int);

int main()
{
	int data[] = {36, 24, 10, 6, 12};

	// call
	InsertionSort(data, 5);	

	// output
	for(int i=0; i<5; i++)
		cout << data[i] << " ";
	cout << "\n\n";	

	return 0;
}

//---------------------------------------
void Swap(int& item1, int& item2)
{
	int temp = item1;
	item1 = item2;
	item2 = temp;
}

//----------------------------------------
int InsertItem(int values[], int startIndex, int endIndex)
{
	bool finished = false;
	int current = endIndex;
	bool moreToSearch = (current != startIndex);

	while(moreToSearch && !finished)
	{
		if( values[current] < values[current-1])
		{	
			Swap(values[current], values[current-1]);
			current --;
			moreToSearch = (current != startIndex);
		}
		else
			finished = true;
	}
}

//----------------------------------------
void InsertionSort(int values[], int numValues)
{
	for(int count=0; count<numValues; count++)
		InsertItem(values, 0, count);
}