How do I change the H sequence in this shell sort?

549 Views Asked by At

I'd like to be able to modify this code so that it uses Knuth's H sequence instead of this one. If anyone could help, I'd greatly appreciate it.

public class ShellSort {
    static int iterations = 0;
    static void insert(double[] a, int h, int r, double v) {
            int i = r - h;
            while (i >= 0 && a[i] > v) {
                a[i+h] = a[i]; i = i - h;
                iterations ++;
            }
            a[i+h] = v;
    }

    static void version0(double[] a, int p, int q) {
        int h;
        h = 1;
        for (int i = p + h; i < q; i++) {
            insert(a, h, i, a[i]);
        }
    }

    public static void main(String[] argv) {
        int size = Integer.parseInt(argv[0]);
        double a[] = new double[ size ];
        for (int i = 0; i < a.length; i++) {
            a[ i ] = Math.random();
            System.out.println(i + " " + a[ i ]);
        }

        version0(a, 0, a.length);

        for (int i = 0; i < a.length; i++) {
            System.out.println(i + " " + a[ i ]);

        }
        System.out.println("Iterations "+ iterations);
    }
}
1

There are 1 best solutions below

0
On

For the sequence 1,2,4,8,16 I believe this may be correct? Replacing the version0 class with this:

static void version1(double[] a, int p, int q) {
int h;
for (h = 1; h <= a.length / 2; h = 2 * h)
/* nothing */ ;
    for ( ; h > 0; h = h / 2) {
        for (int i = p + h; i < q; i++) {
            insert(a, h, i, a[i]);
        }
    }
}