I am trying to modify my shell sort algorithm to use Hibbard's increments rather than n/2.

I know that Hibbard's increments are 2k - 1, but I can't figure out how to incorporate that into my algorithm.

Any suggestions to help me move forward with this? I feel like I just can't figure this one out.

Here's the working version of what I have now, which is NOT using Hibbard's increments:

``````public void shellSort(int[] array, int lowindex, int highindex,
boolean reversed) {
int n = highindex - lowindex;
int increment;
int offset;
for (increment = n / 2; increment > 0; increment = increment / 2) {
for (offset = 0; offset < increment; offset++) {
ShellInsertionSort(array, offset, increment, lowindex,
highindex, reversed);
}
}
for (int ii = 0; ii < array.length; ii++) {
System.out.print(array[ii] + ", ");
}
System.out.println();

}

private static void ShellInsertionSort(int[] array, int offset,
int increment, int lowindex, int highindex, boolean reversed) {
int i, j;
for (i = offset + increment; i <= highindex; i = i + increment) {
int curr = array[i];
for (j = i - increment; j >= 0 && compare(curr, array[j], reversed); j = j
- increment) {
array[j + increment] = array[j];
}
array[j + increment] = curr;
}

}``````

Here is how you can do so.

``````import java.io.*;
import java.util.*;
import java.lang.*;
public class HibbardSort
{
public static void main(String[] args)
{
int j;
int temp;
int i;
int a[]= {13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10,56,78,91,23,144,123,121,223,987};
System.out.println("Given input is");
for(int l=0; l < a.length ; l++)
{
System.out.print(a[l]+",");
}
int inc = 1; …``````

## All 4 Replies

Here is how you can do so.

``````import java.io.*;
import java.util.*;
import java.lang.*;
public class HibbardSort
{
public static void main(String[] args)
{
int j;
int temp;
int i;
int a[]= {13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10,56,78,91,23,144,123,121,223,987};
System.out.println("Given input is");
for(int l=0; l < a.length ; l++)
{
System.out.print(a[l]+",");
}
int inc = 1;
int k = 0;
while (inc <= a.length+1)
{
for (i = inc; i<=a.length-1;i++)
{
temp = a[i];
j = i;
while ( j>=inc && a[j-inc]>temp)
{
a[j] = a[j-inc];
j = j - inc;
}
a[j]=temp;
}
k = k + 1;
inc = (int)(java.lang.Math.pow(2,k))-(int)1;
}
System.out.println("Required output is");
for(int l=0; l < a.length ; l++)
{
System.out.print(a[l]+",");
}
}
}``````

I see how you used Hibbard's increments in your example, but I'm sure what I would need to do to add it to my implementation.

I need to find the initial value, and then properly decrease the amount each time through the loop (if the range of elements contains 100 elements, the first sort would be a 63-sort, followed by a 31-sort, 15-sort, 7-sort, 3-sort and 1-sort).

I'm just not sure how to add this into the current implementation.

To find the initial value, this is the formula according to your program:
replace:
for (increment = n / 2; increment > 0; increment = increment / 2)
for
for (increment = 2^INT[LOG(n)/LOG(2)]-1 ; increment > 0; increment = increment / 2)
LOG(n)/LOG(2) means logaritm base 2 of n

I'd like to point out that ShellSort should consume decremental gaps.
camocspro' nice implementation increases the gaps, which mislead the advantages of this Sorting Algorithm.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.20 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.