1. ## shell sort

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;

}```

2. well, no one replied, but I've figured it out and am posting this just for completeness....maybe someone will need it someday. Change values of n to see the different times.

the prog is written in vc++6.0 and runs fine there...it does not, however, run in g++

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 = 500000;	//n, number of elements

/*****************************************************************
Shell's increments, run for 100 times
******************************************************************/
for( count=0; count < 100; 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 < 100; 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 < 100; 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 )
{
clock_t start, finish;
start = clock();
int j;
for( int i = log(2*n - 1)/log(3), gap = (pow(3,i--) + 1)/2 ; gap >=1 ; gap = (pow(3,i--) + 1)/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;
}```