# Which of these two shuffle algorithms is more random?

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.

• Welcome to Programmers SE. Please notice that questions cannot be opinion-based, since there would be no response which could concisely answer your question. Consider editing your question in order to ask something which can be answered precisely (an example being, "Which shuffle method is more random?").
– Neil
Commented Sep 19, 2013 at 9:01
• @Neil, tnx for pointing that out. I've edited the question. Commented Sep 19, 2013 at 9:08
• I'll retract my close vote then. Thanks for fixing that. :)
– Neil
Commented Sep 19, 2013 at 10:15
• Make a statistic for a lot of test-runs and analyze the measured distribution, if it satisfies your requirements to 'randomness'. Commented Sep 19, 2013 at 11:44
• @Neil: How do you retract your close vote? I haven't been able to do this on SE (beta) sites where I have high rep. Commented Sep 19, 2013 at 17:11

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.

• @ratchet_freak, I appreciate your answer, but there's no need to be rude. I know that guys who wrote shuffle algorithm are probably smarter than I'm, but that wasn't my question. Second I want to shuffle array, but in an efficient way, and your solution is not, since first I convert array to list, then inside shuffle method it gets converted to array that gets shuffled, and after shuffle i need to convert it back to array. Commented Sep 19, 2013 at 10:13
• @robosoul the asList just provides a fixed length facade where each set gets propagated back to array. The returned list there implements randomAccess so shuffle doesn't convert back to an array and shuffles in-place. Told you they were smart ;) Commented Sep 19, 2013 at 10:22
• @ratchet_freak, nice come back. "Told you they were smart ;)" made me laugh :D Nice one :) Appreciate the extra effort. Thank you :) Commented Sep 19, 2013 at 10:30
• @robosoul: I don't think ratchet freak was rude, it's a common thing that we say about implementers of core libraries in several languages. Just like saying that your compiler is smarter than you are. Maybe it's a weird idiom and not the nicest, but I don't think that was a personal thing or an assumption based on your code snippet. Then again, maybe I'm wrong and the freak thinks you're a dumbass. Commented Sep 19, 2013 at 13:34

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.

• +1 - for being informative. This doesn't directly answer the OP's question, but it does at a deeper level by pointing out the right way to implement this. Commented Sep 19, 2013 at 9:56
• this answer would be complete if you point out that this is exactly what version 1 is Commented Sep 19, 2013 at 10:24