Which of these two shuffle algorithms is more random?

Question

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.

Answer 1

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.

Answer 2

Assuming that your random number generator is sufficiently robust, then the optimal algorithm is the Fisher–Yates shuffle

The algorithm can be summarised as this :-

Given a list of items numbered from 1 to N
Pick a random item between 1 and N and swap with item N
Pick a random item between 1 and N-1 and swap with item N-1
...
Pick a random item between 1 and 2 and swap with item 2.

Of course if the selected item is already in position then there's no need to swap.

The key point is to avoid swapping an item again, once it has been placed in position. See here for a discussion on the bias that can be introduced if you do.