Sorting Comparison(revised?)

A.Second Edition
This is second edition of fourth assignment of comp352. And there is almost no improvement at all except comments.
B.The problem
C.The idea of program
        1. First of all, I am highly unsatisfied with this assignment! It is not well-designed.
It is actually a project suggestion in book and I just wonder if professor tried his
program anyway. He told me so, but I am not convinced. Though I suspected that I might
have made some mistakes, however, as long as I have not found out them I am not convinced.
2. It is a painful thing to call 7 sorting algorithm without putting them into an array.
I just don't get it! The compiler sometimes works, sometimes fails. I did a test to put the
template function into an array by declare a function pointer for each of them. This works
in my test program by "instanciating" the template function. But when I did the same thing
here, it failed again! The template feature is indeed , as described professor Grogono,
"an add-on".
3. Experiment "threshold" is really painful! When the size is 40000 or 80000, the 10-test
just run too long! Say one threshold-testing will cost me more than 10 or 20 minutes! That's
why I highly suspect professor did try his program for quicksort2.
กก
D.The major functions
C.Further improvement
กก
/*/////////////////////////////////////////////////////////////////////////
author: qingzhe huang
date: Nov. 23, 2003
purpose: To compare different sorting algorithms
idea of program:
	1. First of all, I am highly unsatisfied with this assignment! It is not well-designed.
	It is actually a project suggestion in book and I just wonder if professor tried his
	program anyway. He told me so, but I am not convinced. Though I suspected that I might
	have made some mistakes, however, as long as I have not found out them I am not convinced.
	2. It is a painful thing to call 7 sorting algorithm without putting them into an array.
	I just don't get it! The compiler sometimes works, sometimes fails. I did a test to put the
	template function into an array by declare a function pointer for each of them. This works 
	in my test program by "instanciating" the template function. But when I did the same thing
	here, it failed again! The template feature is indeed , as described professor Grogono,
	"an add-on".
	3. Experiment "threshold" is really painful! When the size is 40000 or 80000, the 10-test
	just run too long! Say one threshold-testing will cost me more than 10 or 20 minutes! That's
	why I highly suspect professor did try his program for quicksort2.

*/////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <time.h>

using namespace std;


class Compare 
{
public:
	static bool lt(int x, int y) { return x < y; }
	static bool eq(int x, int y) { return x == y; }
	static bool gt(int x, int y) { return x > y; }
};

// Swap two elements in a generic array
template<class Elem>
inline void swap(Elem A[], int i, int j)
{
	Elem temp = A[i];
	A[i] = A[j];
	A[j] = temp;
}

double compCount=0;
double moveCount=0;
int threshold=1;
double minComp, maxComp;
double minMove, maxMove;
long totalComp, totalMove;

int buffer[80000];

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

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();
	threshold = 9;
	test(10000);
	threshold=7;
	test(20000, true);
	threshold =6;
	test(40000);
	threshold =5;
	test(80000);
	return 0;
}

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<<sortName[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<4; i++)
	{
		//this is the first test to show the intermediate step
		if (toShow)
		{
			cout<<"for size of "<<size<<" and sorting method of "
				<<sortName[i]<<endl;
		}
		totalComp=totalMove=0;
		for (int count=0; count<10; count++)
		{
			fillArray(buffer, size);
			sortBy(i, size);
			if (count==0)
			{
				minComp=maxComp=compCount;
				minMove=maxMove=moveCount;
			}
			
			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()%n + i +1;
		Elem pivotElement = A[pivotindex]; //one movement
		swap(A, pivotindex, j); //3 moves
		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++;//one move
	}
	// 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; 
}


And in order to find out threshold, I wrote, or extracted, a simple program here:



	
#include <iostream>
#include <time.h>

using namespace std;

double compCount=0;
double moveCount=0;
//int qukCount=0;
//int insCount=0;
int threshold=1;



class Compare {
public:
  static bool lt(int x, int y) { return x < y; }
  static bool eq(int x, int y) { return x == y; }
  static bool gt(int x, int y) { return x > y; }
};

// Swap two elements in a generic array
template<class Elem>
inline void swap(Elem A[], int i, int j) {
  Elem temp = A[i];
  A[i] = A[j];
  A[j] = temp;
}

int buffer[80000];


template<class Elem, class Comp>
void inssort(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);


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


void experiment(int size, int index);


int main()
{
	srand(time(0));
//	experiment(10000, 0);
//	experiment(20000, 0);
	experiment(40000, 0);
//	experiment(80000, 0);


	return 0;
}

long do10Test(int size)
{
	long total=0;
	for (int i=0; i<10; i++)
	{
//		qukCount=insCount=0;
		fillArray(buffer, size);
		quksort2<int, Compare>(buffer, size);
		total+=compCount;
		total+=moveCount;
	}
//	cout<<"quksort:"<<qukCount/10<<endl;
//	cout<<"inssort:"<<insCount/10<<endl;

	return total/10;
}



void experiment(int size, int index)
{
	long do10Test(int size);//declaration of a utility function

	int minimum=0, current;
	for (int i=6; i<9; i++)//threshold starting at one
	{
		threshold = i;
		current = do10Test(size);
		cout<<"\nNow starts with i="<<i<<endl;
		if (i==6)
		{
			minimum = current;
		}
		else
		{			
			if (current<minimum)
			{
				minimum = current;
				cout<<minimum<<" is threshold"<<endl;
			}
		}
	
		cout<<"current="<<current<<" and minimum="<<minimum<<endl;
	}
	cout<<minimum<<" is threshold"<<endl;
}
			



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>
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 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()%n + i +1;
		Elem pivotElement = A[pivotindex]; //one movement
		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);
//	qukCount+=compCount+moveCount;
	inssort<Elem, Comp>(A, n);
//	insCount+=compCount+moveCount-qukCount;
}





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