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