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;
		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;
			//Adding hilbert increments of 2^k-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.

This question has already been answered. Start a new discussion instead.