//
//	p.629 Quick sort
//
// 	O(NlogN)
//

#include <iostream>
using namespace std;

// prototypes
void Swap(int&, int&);
void QuickSort(int[], int,  int);
void Split(int[], int, int, int&);

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

	// call
	QuickSort(data, 0, 5);	

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

	return 0;
}

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

//----------------------------------------
void QuickSort(int values[], int first, int last)
{
	if(first < last)	
	{
		int splitPoint;		// index
		Split(values, first, last, splitPoint);
		//    .....(<pivot)   pivot(splitVal) ..... (>pivot)
		QuickSort(values, first, splitPoint-1);
		QuickSort(values, splitPoint+1, last);	
	}
}

//----------------------------------------
// p.630
void Split(int values[], int first, int last, int& splitPoint)
{
	int splitVal = values[first];	// pivot
	int saveFirst = first;
	bool onCorrectSide;
	
	first ++;
	do
	{
		onCorrectSide = true;
		while( onCorrectSide )
		{
			if(values[first] > splitVal)
				onCorrectSide = false;
			else
			{
				first ++;
				onCorrectSide = (first <= last);
			}
		}
		onCorrectSide = (first<last);
		while(onCorrectSide)
		{
			if(values[last] <= splitVal)
				onCorrectSide = false;
			else
			{
				last --;
				onCorrectSide = (first <= last);
			}
		}
		if(first < last)
		{
			Swap(values[first], values[last]);
			first ++;
			last --;
		}
	} while(first <= last);
	splitPoint = last;
	Swap(values[saveFirst], values[splitPoint]);
}