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