0

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.