//Yap Hui Wen
//99006448
//Data Structures 2 Assignment 3
//Lecturer: Mr. Elsadig
/*********************************************************************************************/
/*Write a C++ program that computes the time required to sort a randomly generated list using*/
/*Quick Sort and Binary Search Tree Sort                                                     */
/*-Generate the largest possible list of random float values                                 */
/*-Sort the list using BST & QS                                                              */
/*-Compute the time needed in each case                                                      */
/*Write a short note                                                                         */
/*********************************************************************************************/

#include<iostream.h>
#include<time.h>
#include<stdlib.h>
const int MAX=6000;			//maximum list size	
typedef float DataType;
struct node{
	DataType data;
	node* LChild;
	node* RChild;
};
/******************************************************************/
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;
}
/******************************************************************/
int insert (node* &tree, DataType num)
{
	if (tree == NULL)		//tree is empty
	{
		tree = new node;
		tree->LChild = NULL;
		tree->RChild= NULL;
		tree->data= num;
		return 0;
	}
	else if (num == tree->data)
		return insert(tree->LChild,num);	// tree is not empty
	else if (num <= tree->data)
		return insert(tree->LChild,num);
	else 
		return insert(tree->RChild,num);
}
/******************************************************************/
void Inorder(node* tree)
{
	if(tree!=NULL)
	{
		Inorder(tree->LChild);
		Inorder(tree->RChild);
	}
}
/******************************************************************/
int main()
{
	clock_t QS1, QS2, BST1, BST2;			//variable for computing time used
	DataType a[MAX];						//array for quick sorting
	DataType value;
	node* tree=NULL;

	for(int j=0;j<MAX;j++){
		value=rand()%100+0.001;
		a[j]=value;
		insert(tree, value);
	}

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

	BST1=clock();
	Inorder(tree);
	BST2=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<<"*   BST Sort         *        "<<BST2-BST1<<"            *\n";
	cout<<"**********************************************************\n";
	cout<<endl;
	return 0;
}