Population

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