//
// demonstrates a QuickSort sorting algorithm
//
// Algorithm taken from the pseudo code presented in p.154:
//		Cormen, Thomas H., et al.  Introduction to Algorithms.  
//		The MIT Press, 1990.
//		
//
// 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


int Partition (int* A, int p, int r)
{
	int x = A[p];	// this is the pivot value ... any value between the highest and lowest would work as well (e.g. A[(p+r)/2])
	int i = p-1;	// we start i one index below, because when we scan right we increment first, then test
	int j = r+1;	// same reason we start j one index above
	while (true)
	{
		do { j--; }		// start right, scan left until a value less than x is found
		while (A[j] > x);

		do { i++; }		// start left, scan right until a value greater than x is found
		while (A[i] < x);

		if (i < j)
		{	// exchange A[i] with A[j]
			int temp = A[i];  A[i] = A[j];  A[j] = temp;
		}
		else
			return j;
	}
}

void QuickSort (int* A, int p, int r)
{
	if (p < r)
	{
		int q = Partition (A, p, r);
		QuickSort (A, p, q);
		QuickSort (A, q+1, r);
	}
}


//
// 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 ++)
	{
		array[i] = rand() % numElements; // keep numbers in the range of 0-numElements
	}

	// sort the array
	QuickSort (array, 0, numElements-1);

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

	return 0;
}