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


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 4 of 4

Thread: Hibbard Shell Sort

  1. #1
    Junior Member
    Join Date
    Nov 2009
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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. #2
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default 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. #3
    Junior Member
    Join Date
    Nov 2009
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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. #4
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default 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
    }

Similar Threads

  1. How to Sort an Array using the java.util.Arrays class
    By JavaPF in forum Java SE API Tutorials
    Replies: 2
    Last Post: May 17th, 2014, 01:16 AM
  2. Replies: 6
    Last Post: October 20th, 2009, 06:33 AM
  3. Arrays.sort or iterative search?
    By igniteflow in forum Collections and Generics
    Replies: 1
    Last Post: September 16th, 2009, 02:07 AM
  4. Help with Sort arrays
    By drk in forum Collections and Generics
    Replies: 5
    Last Post: September 6th, 2009, 02:48 AM
  5. Insert sort algorithm
    By Alysosh in forum Algorithms & Recursion
    Replies: 1
    Last Post: May 26th, 2009, 09:28 AM

Tags for this Thread