// quicksort10.cpp
// Quicksort on ten numbers
// Programmer: A.H.Dawson
// Last updated: Wednesday 17th November 2004, 13:41 PT

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


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

const int size = 10;

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

int main()
{

	int array [10] = {3,2,4,9,2,8,2,3,6,1};
   display(array,size);

//	Sort the list
	Sort(array, size);



	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) {
	display(A,size);
	if (left < right) {
		int k = Partition(A, left, right);
		QuickSort(A, left, k-1);
		QuickSort(A, k+1, 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]);
         display(A,size);
         getch();
		}
	} 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;
}