// quicksort_timed.cpp
// Quicksort on a set of random numbers
// with timing function
// Programmer: A.H.Dawson
// Last updated: Wednesday 17th November 2004, 13:41 PT


#include <iostream>
#include <cstring>
#include <stdlib>
#include <time>
#include <conio.h>



//	Function prototypes

void Sort(int list[], int size);
void Swap(int &x, int &y);
void display(int x[ ], int size );

/************************************************************************
*																		*
*	Function:	main													*
*																		*
*	Purpose:	To sort a list of numbers into ascending order			*
*																		*
************************************************************************/

int main()
{
	srand((unsigned int) time(0));
	
//	Get size of list

	cout << "Enter the size of the list:  " << flush;
	int size;
	cin >> size;
	
	int* array = new int[size];

//	Create an array of random integers

	for (int i = 0; i < size; i++)
		array[i] = rand();
      //array[i] = rand() % 100; // random number in range 0 - 99

	display(array,size);

//	Get the start time

	int start = clock();

//	Sort the list

	Sort(array, size);

//	Get the stop time

	int stop = clock();

   display(array,size);
//	Report the results

	cout << "Elapsed time = " << (stop - start) << " ticks" << endl;
	
	cout << endl << "Good-bye" << endl;
   getch();
	return 0;
}

//**************************************************************************//
//                                                                          //

void Sort(int A[], int Size);
void QuickSort(int A[], int left, int right);
void Pivot(int A[], int left, int right);
int  Partition(int A[], int left, int right);
void Swap(int &Value1, int &Value2);

// Sort routine
void Sort(int A[], int Size) {
	QuickSort(A, 0, Size - 1);
	return;
}

// QuickSort(): sort using variation of Hoare’s method
void QuickSort(int A[], int left, int right) {
	if (left < right) {
		Pivot(A, left, right);
		int k = Partition(A, left, right);
		QuickSort(A, left, k-1);
		QuickSort(A, k+1, right);
	}
}

// Pivot(): prepare A for partitioning
void Pivot(int A[], int left, int right) {
	if (A[left] > A[right])
		Swap(A[left], A[right]);
}

// Partition(): rearrange A into 3 sublists, a sublist
// A[left] to A[j-1] of values less than A[j], a sublist
// A[j], and a sublist A[j+1] to A[right]
int Partition(int A[], int left, int right) {
	int pivot = A[left];
	int i = left;
	int j = right+1;
	do {
		do ++i; while (A[i] < pivot);
		do --j; while (A[j] > pivot);
		if (i < j) {
			Swap(A[i], A[j]);
		}
	} while (i < j);
	Swap(A[j], A[left]);
	return j;
}

// Swap(): interchange elements
void Swap(int &Value1, int &Value2) {
	int RememberValue1 = Value1;
	Value1 = Value2;
	Value2 = RememberValue1;
}

void display(int x[ ], int size )
{

  int i;
  for( i = 0; i < size; i++ )
     cout << x[i] << ' ';
  cout << endl;
}