//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//@       Yap Hui Wen           @
//@        99006448             @
//@     IFDS Assignment 4       @
//@ Last Edited: 24 March 2002  @
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
#include<iostream.h>
#include<time.h>
#include<stdlib.h>
const int MAX=200000;			//maximum list size
/******************************************************************/
int Acceptlist(int i)
{
	int value[MAX];
	cin>>value[i];
	return value[i];
}
/******************************************************************/
//Display Unsorted List
void DisplayUnsortedList(int unsorted[],int size)
{
	cout<<"Unsorted List:\n=======\n";
	for(int z=0;z<size;z++)
		cout<<unsorted[z]<<"  ";
}
/******************************************************************/
template <typename ElementType>
void QuickSort(ElementType x[], int first, int last)
{
	int pos;				//position of pivot
	if(first<last)			//list has more than one element
	{
		//split into two sublists
		Split(x,first,last,pos);
		//sort left sublist
		QuickSort(x,first, pos-1);
		//sort right sublist
		QuickSort(x, pos+1,last);
	}
	//else list has 0 or 1 element and require no sorting
	return ;
}
/******************************************************************/
template <typename ElementType>
void Split(ElementType y[],int first, int last, int &pos)
{
	ElementType pivot=y[first];			//pivot element
	int left=first;						//index for left search
	bool onCorrectSide;
	++first;

	do{
		onCorrectSide=true;
		while (onCorrectSide){			//move from left to right
			if(y[first]>pivot)
				onCorrectSide=false;
			else{
				++first;
				onCorrectSide=(first<=last);
				}
		}
		onCorrectSide=(first<=last);
		while(onCorrectSide){			//move from right to left
			if(y[last]<=pivot)
				onCorrectSide=false;
			else{
				--last;
				onCorrectSide=(first<=last);
				}
		}
		if(first<last)
		{
			Swap(y[first],y[last]);
			first++;
			last--;
		}
	}while(first<=last);
	pos=last;
	Swap(y[left],y[pos]); //MOVE PIVOT TO END OF LEFT PARTITION!!!!
}
/******************************************************************/
template<typename ElementType>
void Swap(ElementType &a,ElementType &b)
{
	ElementType temp=a;
	a=b;
	b=temp;
}
/******************************************************************/
//Display Sorted List
void Display(int listb[],int e)
{
	cout<<"Sorted List:\n=======\n";
	for(int q=0;q<e;q++)
		cout<<listb[q]<<"  ";
}
/******************************************************************/
int main(){
	clock_t QS1, QS2;
	int list[MAX];
		for(int j=0;j<MAX;j++)
		list[j]=rand()%100;
	cout<<endl<<endl;
	QS1=clock();
	QuickSort(list,0,MAX-1);
	QS2=clock();
	cout<<"\nTime Used: "<<QS2-QS1;
	cout<<endl;
	return 0;
}