Population

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;
    }