shell sort

This is a discussion on shell sort within the C++ Programming forums, part of the General Programming Boards category; one of my assignemnts is to compare the actual running times of different increments when using shellsort - more specifically: ...

  1. #1
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572

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

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  2. #2
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    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;
    }

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Straight Insertion Sort function problem
    By StaticKyle in forum C++ Programming
    Replies: 6
    Last Post: 05-12-2008, 04:03 AM
  2. Shell sort
    By slippy in forum C++ Programming
    Replies: 3
    Last Post: 12-21-2007, 12:07 PM
  3. Shell Sort with Vectors Problem
    By TheSpoiledMilk in forum C++ Programming
    Replies: 4
    Last Post: 11-22-2005, 02:05 PM
  4. Shell, Heap and Quick Sort
    By GaPe in forum C Programming
    Replies: 1
    Last Post: 08-19-2003, 01:04 PM
  5. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 07:05 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21