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