LinkBack URL
About LinkBacks
one of my assignemnts is to compare the actual running times of different increments when using shellsort - more specifically: shell's, hibbard's and Knuth's. Shell's and Hibbard's I've managed to figure out without any problems, but Knuth's seems to be wrong since it give me a much bigger time than the other two, when in fact it is supposed to be faster.
The formula for Knuth's is: hi = (1/2)(3^i + 1 ) ....
any ideas?
BTW: n is set to 50,000 and each test runs only 5 times instead of a 100.
Code:#include <iostream> #include <vector> #include <cstdlib> #include <ctime> #include <cmath> using namespace std; void populateA( vector<int> &a, int n ); void shellSortS( vector<int> &a, int n, double &timeAve ); void shellSortH( vector<int> &a, int n, double &timeAve ); void shellSortK( vector<int> &a, int n, double &timeAve ); int main() { vector<int> a; int n, count; //counters and such double timeAve = 0.0; double timeTot = 0.0; n = 50000; //n, number of elements /***************************************************************** Shell's increments, run for 100 times ******************************************************************/ for( count=0; count < 5; count++ ) { populateA( a, n ); //populate vector with random ints shellSortS( a, n, timeAve ); //sort timeTot += timeAve; //get total time a.clear(); //clear vector } timeAve=(timeTot/count); //calculate average time cout << endl << "average time for shell's: " << timeAve << endl; /***************************************************************** Hibard's increments, run for 100 times ******************************************************************/ timeAve = 0.0; timeTot = 0.0; for( count=0; count < 5; count++ ) { populateA( a, n ); //populate vector with random ints shellSortH( a, n, timeAve ); //sort timeTot += timeAve; //get total time a.clear(); //clear vector } timeAve=(timeTot/count); //calculate average time cout << endl << "average time for hibbard's: " << timeAve << endl; /**************************************************************** Knuth's increments, run for 100 times *****************************************************************/ timeAve = 0.0; timeTot = 0.0; for( count=0; count < 5; count++ ) { populateA( a, n ); //populate vector with random ints shellSortK( a, n, timeAve ); //sort timeTot += timeAve; //get total time a.clear(); //clear vector } timeAve=(timeTot/count); //calculate average time cout << endl << "average time for Knuth's: " << timeAve << endl; /**************************************************************** Get times for already sorted lists ****************************************************************/ timeAve = 0.0; populateA( a, n ); shellSortS( a, n, timeAve ); shellSortS( a, n, timeAve ); cout << endl << "presorted Shell's: " << timeAve; shellSortH( a, n, timeAve ); cout << endl << "presorted Hibbard's: " << timeAve; shellSortK( a, n, timeAve ); cout << endl << "presorted Knuth's: " << timeAve << endl; return 0; } //================================== void populateA( vector<int> &a, int n ) { srand( time(NULL) ); for( int i=0; i<n; i++ ) { a.push_back(rand()%n); } } //==================================== void shellSortS( vector<int> &a, int n, double &timeAve ) { int j; clock_t start, finish; start = clock(); for( int gap=n/2; gap>0; gap/=2 ) for( int i=gap; i<a.size(); i++ ) { int tmp = a[i]; for( j=i; j>=gap && tmp<a[j-gap]; j-=gap) a[j]=a[j-gap]; a[j]=tmp; } finish = clock(); double duration = (double)(finish-start) / CLOCKS_PER_SEC; timeAve = duration; } //==================================== void shellSortH( vector<int> &a, int n, double &timeAve ) { int j; clock_t start, finish; start = clock(); for( int gap = (2 << (int)(log(n/2)/log(2))) - 1; gap > 0; gap /=2 ) for( int i=gap; i<a.size(); i++ ) { int tmp = a[i]; for( j=i; j>=gap && tmp<a[j-gap]; j-=gap) a[j]=a[j-gap]; a[j]=tmp; } finish = clock(); double duration = (double)(finish-start) / CLOCKS_PER_SEC; timeAve = duration; } //==================================== void shellSortK( vector<int> &a, int n, double &timeAve ) { bool done; int temp; clock_t start, finish; start = clock(); for( int gap = 1; gap <= n/3; (gap = 3*gap + 1)); while (gap > 0) { done = false; while (!done) { done = true; for (int i = n - 1; i >= gap; i--) { if (a[i] < a[i-gap]) { temp = a[i]; a[i] = a[i-gap]; a[i-gap] = temp; done = false; } } } gap /= 3; } finish = clock(); double duration = (double)(finish-start) / CLOCKS_PER_SEC; timeAve = duration; }
