6

Can someone please provide a simple working sample of a shellsort in Java that uses the Knuth Sequence? I looked in several places over the internet but can't find an explanation that works well for me. I understand shellsort on a conceptual level - as it's an insertion sort that is done over a gap that shrinks over time until reaching a gap of 1 - which then is essentially an insertion sort. However the Knuth sequence is (k * 3 - 1)/2 and a list of the first few gaps is usually represented as [1, 4, 13, 40, 121.. and so on].

My question is how would this be implemented? Is the starting gap actually 1, or is it the value generated by this sequence just before it is greater than the size of the list being sorted? If the gap started at 1, the purpose would be defeated if I am understanding shell sort correctly. Could someone pelease shed some light on this? I feel like I've missed something critical for understanding this thing.

Thanks in advance.

2 Answers 2

7

Late answer, but for any future onlookers too lazy to follow links from other answers or if the links break ...

This is a way to implement Knuth algorithm to find initial gap value as well as the remaining gap values in descending order:

// Find initial gap.
gap = 1; 
while gap < arrayLength {
  gap = gap * 3 + 1;
}

// Perform the main sorting logic...

// Somewhere within code, at the end
// of the main sorting logic, find next
// descending gap value.
gap /= 3;

The starting gap is not 1. It is the last highest number calculated before going over the length of the array being sorted.

The divide by 3 piece at the bottom basically goes in reverse order of the calculation that was performed in the while loop, in order to get the next gap value in the sequence, in descending order. This is done each time at the end of the main sorting logic.

Also, the formula is actually (3^k - 1) / 2 and NOT (3k - 1) / 2. The former will result in the correct sequence (1, 4, 13, 40, ...) and the latter an incorrect one.

2

I've found one at http://algs4.cs.princeton.edu/ (see the chapter "Elementary Sorts"). The source code can be found here

The Shell class provides static methods for sorting an array using Shellsort with Knuth's increment sequence (1, 4, 13, 40, ...). For additional documentation, see "http://algs4.cs.princeton.edu/21elementary" (Section 2.1) of "Algorithms, 4th Edition" by Robert Sedgewick and Kevin Wayne.

2
  • This code sample is essentially what I needed to see. However section 2.1 here doesn't actually comment on why the code here initializes the gap variable as the last number in the Knuth sequence that is less than a third the size of the sorted collection: // 3x+1 increment sequence: 1, 4, 13, 40, 121, 364, 1093, ... int h = 1; while (h < N/3) h = 3*h + 1; Are you able to comment on why that is?
    – Dielan
    Commented Oct 26, 2015 at 9:48
  • @Dielan I could suggest you find the video(~10min) where R.Sedgewick explains how it works. Use the phrase "shellsort sedgewick princeton" to search that video. Commented Oct 26, 2015 at 10:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.