Sorting Comparison

A.First Edition
This is first edition of fourth assignment of comp352. And it is quite incomplete. I post it only for version 
purpose.
B.The problem
C.The idea of program
กก
D.The major functions
C.Further improvement
กก
#include <iostream>
#include <time.h>
#include "utility.h"


using namespace std;

int compCount=0;
int moveCount=0;
int threshold=1;
int minComp, maxComp;
int minMove, maxMove;
long totalComp, totalMove;
int threshArray[4];
int buffer[80000];

char* sortName[7] = {"shell", "quick1", "merge", "quick2", "bubble", "insert", "select"  };

char* sortString[3] = {"shell", "quick1", "merge"};

template<class Elem, class Comp>
void inssort(Elem A[], int n);

template<class Elem, class Comp>
void selsort(Elem A[], int n);

template<class Elem, class Comp>
void bubsort(Elem A[], int n);

template <class Elem, class Comp>
void shellsort(Elem A[], int n);

template <class Elem, class Comp>
void quksort(Elem A[], int n); 

template <class Elem, class Comp>
void quksort2(Elem A[], int n);

template <class Elem, class Comp>
void mersort(Elem* array, int n);

void fillArray(int array[], int size);


template <class Elem, class Comp>
void print(Elem A[], int size);

void test(int size, bool toShow=false);

void sortBy(int index, int size);

void testSort();
void output(int index, int size);

void experiment(int size, int index);

int min(int i, int j);
int max(int i, int j);

int main()
{
	srand(time(0));
//	testSort();
//	test(10000);
//	test(20000, true);
//	test(40000);
//	test(80000);
	experiment(10000, 0);
	return 0;
}

long do10Test(int size)
{
	long total=0;
	for (int i=0; i<10l; i++)
	{
		fillArray(buffer, size);
		quksort<int, Compare>(buffer, size);
		total+=compCount;
		total+=moveCount;
	}
	return total/10;
}



void experiment(int size, int index)
{
	long do10Test(int size);

	int minimum=0, current;
	for (int i=1; i<size; i+=5)//threshold starting at one
	{
		threshold = i;
		current = do10Test(size);
		cout<<"i="<<i<<endl;
		cout<<"current="<<current<<" and minimum="<<minimum<<endl;
		if (i==1)
		{
			minimum = current;
		}
		else
		{			
			if (current<minimum)
			{
				threshArray[index]=i;
				minimum = current;
				cout<<threshArray[index]<<" is threshold"<<endl;
			}
		}
	}
	cout<<threshArray[index]<<" is threshold"<<endl;
}
			




int min(int i, int j)
{
	return (i>j)?j:i;
}

int max(int i, int j)
{
	return (i<j)?j:i;
}

void output(int index, int size)
{
	cout<<sortString[index]<<"\t"<<"number of comparison"<<"\tnumber of moves"<<endl;
	cout<<"input size"<<"\tbest\tworst\taverage\t||\tbest\tworst\taverage"<<endl;
	cout<<"N="<<size<<"\t"<<minComp<<"\t"<<maxComp<<"\t"<<totalComp/10<<"\t"
		<<minMove<<"\t"<<maxMove<<"\t"<<totalMove/10<<endl;
}

void test(int size, bool toShow)
{

	for (int i=0; i<3; i++)
	{
		if (toShow)
		{
			cout<<"for size of "<<size<<" and sorting method of "
				<<sortString[i]<<endl;
		}
		for (int count=0; count<10; count++)
		{
			if (count==0)
			{
				minComp=maxComp=compCount;
				minMove=maxMove=moveCount;
				totalComp=totalMove=0;
			}
			fillArray(buffer, size);
			sortBy(i, size);
			
			if (toShow)
			{
				cout<<"test no."<<count+1<<endl;
				cout<<"comparison count:"<<compCount<<endl;
				cout<<"move count:      "<<moveCount<<endl;
			}
			
			minComp = min(compCount, minComp);
			maxComp = max(compCount, maxComp);
			minMove = min(compCount, minMove);
			maxMove = max(compCount, maxMove);
		
			totalMove+=moveCount;
			totalComp+=compCount;
		}
		if (toShow)
		{
			cout<<"total comparison count:"<<totalComp<<endl;
			cout<<"total move  count:     "<<totalMove<<endl;
		}
		output(i, size);	
	}
}

template <class Elem, class Comp>
void print(Elem A[], int size)
{
	for (int i=0; i<size; i++)
	{
		cout<<"no."<<i+1<<": "<<A[i]<<"\n";
	}
}

void sortBy(int index, int size)
{
	switch(index)
	{
	case 0:
		shellsort<int, Compare>(buffer, size);
		break;
	case 1:
		quksort<int, Compare>(buffer, size);
		break;
	case 2:
		mersort<int, Compare>(buffer, size);
		break;
	case 3:
		quksort2<int, Compare>(buffer, size);
		break;
	case 4:
		bubsort<int, Compare>(buffer, size);
		break;
	case 5:
		inssort<int, Compare>(buffer, size);
		break;
	case 6:
		selsort<int, Compare>(buffer, size);
		break;
	}
}

void testSort()
{
	int size =10;
	for (int i=0; i<7; i++)
	{
		fillArray(buffer, size);
		cout<<"\nbefore...\n";
		print<int, Compare>(buffer, size);
		cout<<"sorted by "<<sortName[i]<<endl;
		sortBy(i, size);
		cout<<"\nafter...\n";
		print<int, Compare>(buffer, size);
	}
}

void fillArray(int array[], int size)
{
	for (int i=0; i< size; i++)
	{
		array[i] = rand();
	}
	compCount=moveCount=0;//initialize
}


template<class Elem, class Comp>
void bubsort(Elem A[], int n)
{
	for (int i=0; i<n-1; i++)
	{
		for (int j=n-1; j>i; j--)
		{
			if (Comp::lt(A[j], A[j-1]))
			{
				swap(A, j, j-1);
				moveCount+=3;
			}
			compCount++;
		}
	}
}


template <class Elem>
int findpivot(Elem A[], int i, int j)
{ 
	return (i+j)/2; 
}

template <class Elem, class Comp>
int partition(Elem A[], int l, int r, Elem& pivot) 
{
	do {             // Move the bounds inward until they meet
	while (Comp::lt(A[++l], pivot))
	{
		compCount++;     // Move l right and
	}
	while ((r != 0) && Comp::gt(A[--r], pivot))
	{
		compCount++; // r left
	}
	swap(A, l, r);              // Swap out-of-place values
	moveCount+=3;
	} while (l < r);              // Stop when they cross
	swap(A, l, r);                // Reverse last, wasted swap
	moveCount+=3;
	return l;      // Return first position in right partition
}

template <class Elem, class Comp>
void qsort(Elem A[], int i, int j) 
{ // Quicksort
	if (j <= i) return; // Don't sort 0 or 1 Elem
	int pivotindex = findpivot(A, i, j);
	swap(A, pivotindex, j);    // Put pivot at end
	moveCount+=3;
	// k will be the first position in the right subarray
	int k = partition<Elem,Comp>(A, i-1, j, A[j]);
	swap(A, k, j);             // Put pivot in place
	moveCount+=3;
	qsort<Elem,Comp>(A, i, k-1);
	qsort<Elem,Comp>(A, k+1, j);
}

template <class Elem, class Comp>
void quksort(Elem A[], int n) 
{
	qsort<Elem,Comp>(A, 0, n-1);
}



// Modified version of Insertion Sort for varying increments
template <class Elem, class Comp>
void inssort2(Elem A[], int n, int incr)
{
	for (int i=incr; i<n; i+=incr)
	{
		for (int j=i; j>=incr; j-=incr)
		{
			if (Comp::lt(A[j], A[j-incr]))
			{
				swap(A, j, j-incr);
				moveCount+=3;
			}
			compCount++;
		}
	}
}

template <class Elem, class Comp>
void shellsort(Elem A[], int n) 
{ // Shellsort
	for (int i=n/2; i>2; i/=2)      // For each increment
	{
		for (int j=0; j<i; j++) 
		{
			inssort2<Elem,Comp>(&A[j], n-j, i);  // Sort each sublist
		}
	}
	inssort2<Elem,Comp>(A, n, 1);
}





template<class Elem, class Comp>
void selsort(Elem A[], int n)
{
	for (int i=0; i<n; i++)
	{
		int lowIndex = i;
		for (int j=i+1; j<n; j++)//i don't like loop of decrementing counter
		{
			if (Comp::lt(A[j], A[lowIndex]))
			{
				lowIndex = j;
			}
			compCount++;
		}
		//it is said that you reduce comparison but will increase swap
		//and verse vosa
		swap(A, i, lowIndex);
		moveCount+=3;
	}
}




template<class Elem, class Comp>
void inssort(Elem A[], int n)
{
	for (int i=1; i<n; i++)
	{
		for (int j=i; j>0; j--)
		{
			if (Comp::lt(A[j], A[j-1]))
			{
				swap(A, j, j-1);
				moveCount+=3;
			}
			compCount++;
		}
	}
}


template <class Elem, class Comp>
void qsort2(Elem A[], int i, int j)
{
	int n = j-i+1;
	if (j<=i)
	{
		return;
	}
	if (n>threshold)
	{
		int pivotindex = rand()%(j-i+1);
		Elem pivotElement = A[pivotindex];
		swap(A, pivotindex, j); 
		moveCount+=4;
		int k = partition<Elem, Comp>(A, i, j, pivotElement);
		 
		qsort2<Elem, Comp>(A, i, k-1);
		qsort2<Elem, Comp>(A, k+1, j);
	}
}


template <class Elem, class Comp>
void quksort2(Elem A[], int n)
{
	qsort2<Elem, Comp>(A, 0, n-1);
	inssort<Elem, Comp>(A, n);
}



template <class Elem, class Comp>
void mergesort(Elem A[], Elem temp[], int left, int right)
{
	int mid = (left+right)/2;
	if (left == right)
	{
		return;        // List of one element
	}
	mergesort<Elem,Comp>(A, temp, left, mid);
	mergesort<Elem,Comp>(A, temp, mid+1, right);
	for (int i=left; i<=right; i++)   // Copy subarray to temp
	{
		temp[i] = A[i];
		moveCount++;
	}
	// Do the merge operation back to A
	int i1 = left; 
	int i2 = mid + 1;
	for (int curr=left; curr<=right; curr++)
	{
		if (i1 == mid+1)      // Left sublist exhausted
		{
			A[curr] = temp[i2++];
		}
		else 
		{
			if (i2 > right)  // Right sublist exhausted
			{
				A[curr] = temp[i1++];
			}
			else 
			{
				if (Comp::lt(temp[i1], temp[i2]))
				{
					A[curr] = temp[i1++];
				}		
				else
				{
					A[curr] = temp[i2++];
				}
				compCount++;
			}
		}
		moveCount++;//whatever result the move is always done once
	}
}

template <class Elem, class Comp>
void mersort(Elem* array, int n) {
	Elem* temp = NULL;
	if (temp == NULL)
	{
		temp = new Elem[n];  // Declare temp array
	}
	mergesort<Elem,Comp>(array, temp, 0, n-1);
	delete [] temp; 
}





	


                                 back.gif (341 bytes)       up.gif (335 bytes)         next.gif (337 bytes)