Shell Sort Mod

[dfetter88]

As you probably know, Shell sort is typically written with a base of insertion sort, as shown below:

for (ctr = numGaps - 1; ctr >= 0; ctr--)
  {
    k = gapSeq[ctr];

    /* Insertion Sort Begins Here */
    for (j = k; j < size; j++)
    {
      tmp = array[j];
      i = j;
      while (i >= k && array[i - k] > tmp)
      {
        array[i] = array[i - k];
        i = i - k;
      }
      array[i] = tmp;
    }
  }

I am trying to mod Shell Sort to use selection sort as its base, but I'm running into conceptual problems. Here's what I have right now:

for (ctr = numGaps - 1; ctr >= 0; ctr--)
  {
    k = gapSeq[ctr];

    /* Selection Sort Mod Begins Here */
    for (i = size - 1; i > 0; i--)
    {
      maxIdx = 0;
      for (j = k; j <= i; j += k)
      {
        if (array[j] >= array[maxIdx])
        {
          maxIdx = j;
        }
      }
      tmp = array[i];
      array[i] = array[maxIdx];
      array[maxIdx] = tmp;
    }
  }

I understand that a selection sort basis would be less efficient. When I run through this code in my head, however, the comparisons seem extremely redundant. Is this how it should be? Any help/thoughts/comments would be greatly appreciated.

[dfetter88]

I did a little more investigation into this problem...

I calculated the # of comparisons & the # of data swaps in each of the two models of Shell sort above. As I expected, the selection sort model had far more comparisons. I was surprised, however, to find that the selection sort model had more data swaps than the insertion sort model.

Considering selection sort has O(n) swaps compared to insertion's O(n^2), I'm seeing this as hard evidence my selection sort adaptation is incorrect. I'll continue to try and chip away at this problem, but would love for somebody to help out.

[dfetter88]

Alrighty, figured this one out on my own. I'll post the code for reference.

for (ctr = numGaps - 1; ctr >= 0; ctr--)
  {
    k = gapSeq[ctr];
    for (i = 0; i < size - 1; i++)
    {
      minIdx = i;
      for (j = minIdx + k; j < size; j += k)
      {
        if (array[j] < array[minIdx])
        {
          minIdx = j;
        }
      }
      tmp = array[i];
      array[i] = array[minIdx];
      array[minIdx] = tmp;
    }
  }

I made two changes to help me visualize the problem:
(1) I changed the first for loop to increment, instead of decrement through the array.
(2) I switched the selection sort to search for the minimum element instead of the maximum.

Side note:
The reason I had so many data swaps despite the selection sort was an error on my part. I was adding to the number of data swaps even when 'i' == 'minIdx' (i.e. an array element was swapped with itself).