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.

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.

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).

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.