Thread: 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;

}

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