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.

You don't seem to be using gaps[], you're just use a gap (e) which increments from 0..n-1 ? — Paul R
– Paul R, Commented Mar 5, 2013 at 13:02
@Okan Of course your test code shows nothing! You're setting size to 0 not 9. — anon
– anon, Commented Mar 5, 2013 at 13:14
You missed the fact that the "gaps" array in the article isn't the array to be sorted - it's the "step sizes" of the algorithm. — molbdnilo
– molbdnilo, Commented Mar 5, 2013 at 13:35

anon · Accepted Answer · 2013-03-05 13:30:09Z

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

franji1 · Accepted Answer · 2013-03-15 13:05:39Z

1

For some reason (no comments were given), my first answer was deleted (typo - you set size to 0, not 9). The question wondered why "it shows nothing on the screen". If you set size to 0, what do you expect a for loop to do when it iterates from 0 to < size???

Before looking at the algorithm, your parameters must be correct. Start there. If SOMETHING now gets dumped to the screen, NOW you can start debugging the algorithm (if the output was wrong). If the output is right, then your algorithm is probably okay.

If I am wrong about this, PLEASE POST A COMMENT TO MY ANSWER. Don't just "delete" it!?!

answered Mar 15, 2013 at 13:05

franji1

3,1862 gold badges27 silver badges47 bronze badges

Collectives™ on Stack Overflow

shell sort pseudocode to C++ code

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related