Hibbard Shell Sort

• November 11th, 2009, 11:35 PM
biglandphil
Hibbard Shell Sort
I have gotten down shell sort algorithms, but i just cant get Hibbard's increments. I get what they are, I just cant implement them into my basic shell sort. For other shell sorts, they go while gap>0, but with Hibbard it's counting up... when does it stop?? i figure if it goes while gap<array.length, the gap will eventually over shoot the end of the array?? please help!!
• November 12th, 2009, 10:08 AM
helloworld922
Re: Hibbard Shell Sort
Try computing the values in the increment, then start running from the value that's gap size is less then the length of the array and work your way down to 1.
• November 12th, 2009, 02:02 PM
biglandphil
Re: Hibbard Shell Sort
Yeah that's what I ended up doing, it was just annoying that going low to high didn't work. It sorted it but took much longer than it was supposed to, and only worked for small array sizes. thanks.
• November 12th, 2009, 09:14 PM
helloworld922
Re: Hibbard Shell Sort
Going low to high would do this:

1. Sort with step size 1 (aka. basic insertion sort, O(n^2) worst performance)
2. Sort with step size 3 (already sorted, O(n))
3. Sorted with step size 5 (already sorted, O(n))
...

When you add up all of these performance times, it takes O(n^2 + n + n + n + ... + n), which technically boils down to O(n^2), but is considerable slower.

It's very easy to compute the step size:

Code :

```for (int step = array.length() - array.length() % 2 - 1; i > 1; i -= 2) { // insertion sort stuff with incrementing by step }```