shell sort in C++ with Ciura gap sequence

Question

I had a assignment due for class and have this code I turned in but I am not really sure if I did it correctly and would like some input from anyone who is knowledgeable with this problem.
He assigned us the "typical" shell sort file here.

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>

using namespace std;


template <typename Comparable>
unsigned long shellsort( vector<Comparable> & a )
{
  unsigned long counter = 0;

  for( unsigned int gap = a.size( ) / 2; gap > 0; gap /= 2 )
    for( unsigned int i = gap; i < a.size( ); i++ )
    {
      Comparable tmp = a[ i ];
      unsigned int j = i;

      for( ; j >= gap ; j -= gap )
      {
        counter++;
        if (!(tmp < a[ j - gap ])) break;
        a[ j ] = a[ j - gap ];
      }

      a[ j ] = tmp;
    }

  return counter;
}

const int N = 10000;

int main ()
{
  vector<int> rnumbers;
  clock_t start, finish;
  double duration;

  srand(42);
  start = clock();

  cout << "Sorting " << N << " numbers." << endl;

  for (int i=0; i<N; i++)
    rnumbers.push_back (rand ());

  finish = clock();
  duration = (double)(finish - start) / CLOCKS_PER_SEC;

  cout << "Initializing vector: " << duration << " seconds." << endl;

  start = clock();

  unsigned long comp = shellsort (rnumbers);

  finish = clock();
  duration = (double)(finish - start) / CLOCKS_PER_SEC;

  cout << "Sorting vector: " << duration << " seconds." << endl;
  cout << "Number of comparisons: " << comp << endl;

  return 0;
}

and we next had to use modify the code to accommodate different gap sequences which are the Ciura optimal gap sequences and then calculate the numbers farther but under 1 million using the formula.

int c[] = {510774, 227011, 100894, 44842, 19930, 8858, 3937, 1750, 701, 301, 132, 57, 23, 10, 4, 1};

He stated to modify the code so I only modified this part.

  unsigned long counter = 0;
  int x=0;
  int c[16] = {510774, 227011, 100894, 44842, 19930, 8858, 3937, 1750, 701, 301, 132, 57, 23, 10, 4, 1};
  for( unsigned int gap = c[x]; gap > 0; gap /= 2 )
  {
      x++;
    for( unsigned int i = gap; i < a.size( ); i++ )
    {

I it still sorts and has no errors but I cant help but think by modifying the code like I did, I did not really achieve anything that it was already doing before.

if anyone could help me I would greatly appreciate it.

Thanks in advance.

Answer 1

Instead of computing the next gap value by doing gap /= 2 you should be iterating over the Ciura sequence and using each value in turn as the gap. So instead of doing:

for( unsigned int gap = c[x]; gap > 0; gap /= 2 )

Try something like:

for( int x = 0; x < 16; ++x )
{
    unsigned int gap = c[x];
    ...