shell sort pseudocode to C++ code

Question

# Sort an array a[0...n-1].
gaps = [701, 301, 132, 57, 23, 10, 4, 1]

foreach (gap in gaps)
    # Do an insertion sort for each gap size.
    for (i = gap; i < n; i += 1)
        temp = a[i]
        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
            a[j] = a[j - gap]
        a[j] = temp

this is the pseudocode in Wikipedia page. I'm not sure about that if my c++ code is correct according to it. Here is my code:

void shellSort(int *array, int array_size)
{
  int e, i, j, temp;
  for(e = 0; e < array_size; e++)
  {
      for( i = e; i < array_size; i++)
      {
          temp = array[i];
          for( j = i; j >= e && array[j - e] > temp; j -= e)
          {
             array[j] = array[j-e];
          }
          array[j] = array[temp];
      }

  }
}

And here is my test code:

int main()
{
    int sizes[9] = {9,3,5,7,1,0,6,2,4};
    int size = 0;
    shellSort(sizes,size);

    for(int i=0;i<size;i++)
    {
        cout << sizes[i] << endl;
    }

return 0;

}

but it shows nothing on the screen.

Answer 1

Okay, let's take this from the top

void shellSort(int *array, int array_size)
{

Your code completely omitted the needed gaps array

  const int gaps[] = {701, 301, 132, 57, 23, 10, 4, 1};
  int e, i, j, temp;

The outer loop needs to be across gaps rather than 0 to array_size

  for(e = 0; e < sizeof(gaps)/sizeof(int); ++e)
  {
      int gap = gaps[e];

You need to use the gap from the gaps array in the inner loop

      for( i = gap; i < array_size; ++i)
      {
          temp = array[i];
          for( j = i; j >= gap && array[j - gap] > temp; j -= gap)
          {
             array[j] = array[j-gap];
          }

You need to store temp back into the array

          array[j] = temp;
      }

  }
}

NB: I don't have a compiler to hand right now, so I haven't checked that, but I think it's right.

Also, a few minor points, this:

  int e, i, j, temp;

is bad practice, instead declare each variable as you use it, i.e. do this instead:

      for( int i = gap; i < array_size; ++i)
      {
          int temp = array[i];