Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

1. ## 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!!

2. ## 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.

3. ## 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.

4. ## 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:

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