1

Let's assume we have a sequence a_i of length n and we want to sort it using shell sort. To do so, we would choose sub sequences of out a_i's of length k_i.

I'm now wondering how to choose those k_i's. You usually see that if n=16 we would choose k_1=8, k_2=4, k_3=2, k_4=1. So we would pair-wise compare the number's for each k_i and at the end use insertionSort to finish our sorting.

The idea of first sorting sub sequences of length k_i is to "pre-sort" the sequence for the insertionSort. Right?

Questions:

  1. Now, depending on how we choose our k_i, we get a better performance. Is there a rule I can use here to choose the k_i's?

  2. Could I also choose e.g. n=15, k_1=5, k_2=3, k_3=2?

  3. If we have n=10 and k_1=5, would we now go with {k_2=2, k_3=1} or {k_2=3, k_2=2, k_3=1} or {k_2=3, k_3=1}?

Improve this question

1 Answer 1

Reset to default
4

The fascinating thing about shellsort is that for a sequence of n (unique) entries a unique set of gaps will be required to sort it efficiently, essentially f(n) => {gap/gaps}

For example, to most efficiently - on average - sort a sequence containing

  • 2-5 entries - use insertion sort
  • 6 entries - use shellsort with gaps {4,1}
  • 7 or 8 entries - use a {5,1} shellsort
  • 9 entries - use a {6,1} shellsort
  • 10 entries - use a {9,6,1} shellsort
  • 11 entries - use a {10,6,1} shellsort
  • 12 entries - use a {5,1} shellsort

As you can see, 6-9 require 2 gaps, 10 and 11 three and 12 two. This is typical of shellsort's gaps: from one n to the next (i e n+1) you can be fairly sure that the number and makeup of gaps will differ.

A nasty side-effect of shellsort is that when using a set of random combinations of n entries (to save processing/evaluation time) to test gaps you may end up with either the best gaps for n entries or the best gaps for your set of combinations - most likely the latter.

I speculate that it is probably possible to create algorithms where you can plug in an arbitrary n and get the best gap sequence computed for you. Many high-profile computer scientists have explored the relationship between n and gaps without a lot to show for it. In the end they produce gaps (more or less by trial and error) that they claim perform better than those of others who have explored shellsort.

Concerning your foreword given n=16 ...

  • a {8,4,2,1} shellsort may or may not be an efficient way to sort 16 entries.
  • or should it be three gaps and, if so, what might they be?
  • or even two?

Then, to (try to) answer your questions ...

Q1: a rule can probably be formulated

Q2: you could ... but you should test it (for a given n there are n! possible sequences to test)

Q3: you can compare it with the correct answer (above). Or you can test it against all 10! possible sequences when n=10 (comes out to 3628800 of them) - doable

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

I think your n! answer to Q2 is an over-estimate. The gap is monotonically decreasing; if you select (n-6) as the first gap, you can't use any of (n-1)..(n-5) as another step. I'm not sure how much of an over-estimate that makes it.
I've seen a shell sort gap-selection scheme (from Sedgewick "Algorithms" — in Pascal) where they calculate gaps using a scheme similar to gap[i] = gap[i-1]*3 + 1 and they keep going until the gap is bigger than the data set and start from there. I think that's 1, 4, 13, 40, 121, … I dunno whether that does more than confirm that there are many ways to determine shell sort gaps, and many of those work. And I've collected some other variations on gap-deciding.
n! is not an overestimate for a sequence of n values. A sequence of length n=2 can be sorted in 2! = 2 ways 01 and 10. n=3 gives 6 ways or 012, 021, 102, 120, 201 and 210. If you mean the number of different gap combinations given n the answer is 2^(n-2) so for n=2 there is only one possibility, a gap of {1}. For n=3 there are two possibilities, {2,1} or {1}.
Concerning the shellsort gap selection scheme from Sedgwick is too blunt as it obviously does not produce the gaps for 7-12 listed above.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.