Java – Which of these two shuffle algorithms is more random

algorithmsjavarandom

Which of below two shuffle algorithms (shuffle1 and shuffle2) is more random?

public final class Shuffle {
    private static Random random;

    public static void shuffle1(final Object[] array) {
        if (random == null) {
            random = new Random();
        }

        for (int i = array.length - 1; i > 0; i--) {
            swap(array, i, random.nextInt(i + 1));
        }
    }

    public static void shuffle2(final Object[] array) {
        if (random == null) {
            random = new Random();
        }

        for (int i = 0; i < array.length; i++) {
            swap(array, i, i + random.nextInt(array.length - i));
        }
    }

    protected static void swap(final Object[] array, final int i, final int j) {
        final Object tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}

The shuffle2 algorithm guaranties that all elements are directly touched, but, in shuffle1 algorithm, the element with index = 0 is never directly touched because of the condition i > 0.

Best Answer

If you just want a shuffle then use Collections.shuffle(Arrays.asList(array)); which was written by people smarter than you and me.

As for the guarantee that the first element gets touched consider that in the second algorithm the last step (when i==array.length-1) that you are calling random.nextInt(1) which always return 0 which makes that step meaningless

Beyond that the algorithms are equivalent.

Related Topic