shell sort using Hibbard's increments

[seacase]

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

	}

[camocspro]

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]+",");
		}
	}
}

[seacase]

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.

[javidil]

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

[Mohamed_22]

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.