// Quicksort & Templates
// By: Odis

// You can find some good information on the Quick Sort algorithm at
// http://en.wikipedia.org/wiki/Quick_sort

#include <cstdlib>
#include <iostream>
#include <time.h>

// Comment this out to turn off the array output
//#define DISPLAY_OUTPUT

// Change this to change the number of elements to be stored and sorted
#define ARRAY_LENGTH 60

// forward decl.
template< typename Type, bool ShowPivot >
int partition( Type* array, int low, int high );

template< typename Type, bool ShowPivot>
void quickSort( Type* array, int low, int high )
{
	int pivotPosition = -1;

	if ( low < high )
	{
		pivotPosition = partition<Type, ShowPivot>(array, low, high);
		quickSort<Type, ShowPivot>(array, low, pivotPosition-1);
		quickSort<Type, ShowPivot>(array, pivotPosition+1, high );
	}
}

template< typename Type >
void swap( Type& x, Type& y )
{
	Type temp = x;

	x = y;
	y = temp;
}

template< typename Type, bool ShowPivot >
int partition( Type* array, int low, int high )
{
	int left, right;
	Type pivot;

	left = low;
	right = high;
	pivot = array[low];

	while ( left < right )
	{
		while ( array[right] > pivot )
			right--;

		while ( (left < right) && (array[left] <= pivot) )
			left++;

		if ( left < right )
			swap(array[left], array[right] );
	}

	array[low] = array[right];
	array[right] = pivot;

	if ( ShowPivot )
		std::cout << "I chose position " << right << " as the pivot." << std::endl;

	return right;
}

int main()
{
	int array[ARRAY_LENGTH];
	int length = ARRAY_LENGTH;

	// for timing
	time_t start, end;

	// seed pseudo random number generator
	srand(time(NULL));

	#ifdef DISPLAY_OUTPUT
	std::cout << "\nPicking random elements...\n";
	#endif

	for ( int i = 0; i < ARRAY_LENGTH; i++ )
		array[i] = (rand() % 10000); /*for ints*/
	//     array[i] = (rand() % 26)+(((rand() % 2) == 0) ? 97 : 65); /*for chars*/
	//     array[i] = (rand()/(float(RAND_MAX)+1))*ARRAY_LENGTH; /*for floats*/

	#ifdef DISPLAY_OUTPUT
	// print out unsorted
	std::cout << "\nUnsorted\n\n";
	for ( int i = 0; i < ARRAY_LENGTH; i++ )
	{
		std::cout << array[i];

		// print new lines or comma's
		if ( (i % 10) == 9 )
			std::cout << std::endl;
		else if ( i+1 < ARRAY_LENGTH )
			std::cout << ", ";
	}
	#endif

	time(&start);

	// call the function to get everything started
	quickSort<int, true>( array, 0, length-1 );

	time(&end);

	#ifdef DISPLAY_OUTPUT
	std::cout << "\n\nSorted\n\n";

	for ( int i = 0; i < ARRAY_LENGTH; i++ )
	{
		std::cout << array[i];

		// print new lines or comma's
		if ( (i % 10) == 9 )
			std::cout << std::endl;
		else if ( i+1 < ARRAY_LENGTH )
			std::cout << ", ";
	}
	#else
	std::cout << "\n\nNumber of random elements: " << ARRAY_LENGTH;
	#endif

	std::cout << "\n\nTime: " << difftime(end,start) << std::endl << std::endl;


	return EXIT_SUCCESS;
}