//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//@       Yap Hui Wen                         @
//@        99006448                           @
//@     Data Structures II Assignment 1       @
//@ Last Edited: 24 March 2002                @
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
#include<iostream.h>
#include<time.h>
#include<stdlib.h>
#include<string.h>
const int MAX=60000;			//maximum list size
/******************************************************************/
int Acceptlist(int i)
{
	int value[MAX];
	cin>>value[i];
	return value[i];
}
/******************************************************************/
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;
}
/******************************************************************/
template<typename DataType>
void exchange (DataType a[], int i, int j)
{
	DataType temp=a[i];
	a[i]=a[j];
	a[j]=temp;
}
/******************************************************************/
void insertionSort (int a[])
{
	int i,j;
	for(i=1;i<MAX;i++){
		//attempt to insert a[i] into sorted region
		for(j=i; j>0 && (a[j]<a[j-1]);j--)
			exchange (a,j-1,j);
	}
}

/******************************************************************/
template <typename DataType>
void bubbleSort(DataType a[])
{
	bool change;
	do{
		change=false;
		//next sweep to ensure that
		for(int i=0; i<MAX;i++)
			if(a[i]>a[i+1])
			{
				exchange (a,i,i+1);
				change= true;
			}
	}while (change);
}
/******************************************************************/
template <typename DataType>
void selectionSort( DataType a[])
{
	int i,j;
	for(i=0;i<MAX;i++){
		//find the next smallest in a[i]...a[MAX-1]
		int small=i;
		for(j=i+1;j<MAX;j++)
			if(a[j]<a[small])
				small=j;
			//move the smallest to a[j];
			exchange (a,i,small);
	}
}
/******************************************************************/
int main(){
	clock_t QS1, QS2, IS1, IS2, BS1, BS2, SS1, SS2;
	int a[MAX];	
	int b[MAX];
	int c[MAX];
	int d[MAX];
	
	for(int j=0;j<MAX;j++)
		d[j]=c[j]=b[j]=a[j]=rand()%100;

	QS1=clock();
	quickSort(a,0,MAX-1);
	QS2=clock();

	IS1=clock();
	insertionSort(b);
	IS2=clock();

	BS1=clock();
	bubbleSort(c);
	BS2=clock();

	SS1=clock();
	selectionSort(d);
	SS2=clock();

	cout<<"Sorting an generated list of 60000 random numbers........\n";
	cout<<"**********************************************************\n";
	cout<<"**********************************************************\n";
	cout<<"*     Sort Method    *         Time Taken (clock ticks)  *\n";
	cout<<"**********************************************************\n";
	cout<<"**********************************************************\n";
    cout<<"*   Quick Sort       *        "<<QS2-QS1<<"              *\n";
	cout<<"**********************************************************\n";
	cout<<"*  Insertion Sort    *        "<<IS2-IS1<<"              *\n";
	cout<<"**********************************************************\n";
	cout<<"*  Bubble Sort       *        "<<BS2-BS1<<"              *\n";
	cout<<"**********************************************************\n";
	cout<<"*  Selection Sort    *         "<<SS2-SS1<<"             *\n";
	cout<<"**********************************************************\n";
	cout<<endl;
	return 0;
}