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