PerfectShuffle.java

Below is the syntax highlighted version of PerfectShuffle.java from §9.7 Optimization.

/******************************************************************************
 *  Compilation:  javac PerfectShuffle.java
 *  Execution:    java PerfectShuffle
 *
 *  
 ******************************************************************************/

public class PerfectShuffle {

    // perfect shuffle an array in-place
    public static void perfectShuffle(double[] a) {
        int N = a.length;
        if (Integer.highestOneBit(N) != N) {
            throw new RuntimeException("length is not a power of 2");
        }
        perfectShuffle(a, 0, N);
    }

    // perfect shuffle a[l] to a[r-1]
    // assumes length is a power of 2
    public static void perfectShuffle(double[] a, int l, int r) {
        int N = r - l;
        if (N <= 2) return;
        int m = l + N / 2;
        perfectShuffle(a, l, m);
        perfectShuffle(a, m, r);
        for (int i = 0; i < N / 2; i += 2)
            swap(a, l+1+i, m+i);
    }

    private static void swap(double[] a, int i, int j) {
        double temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }


    // test client
    public static void main(String[] args) { 

        // fill in array
        int N = Integer.parseInt(args[0]);
        double[] a = new double[N];
        for (int i = 0; i < N; i++)
            a[i] = i;

        // perform a perfect shuffle
        perfectShuffle(a);

        // print results
        for (int i = 0; i < N; i++)
            StdOut.println(a[i]);
    }

}