# 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 Sep 19 '13 at 9:01
• @Neil, tnx for pointing that out. I've edited the question. – robosoul Sep 19 '13 at 9:08
• I'll retract my close vote then. Thanks for fixing that. :) – Neil Sep 19 '13 at 10:15
• Make a statistic for a lot of test-runs and analyze the measured distribution, if it satisfies your requirements to 'randomness'. – MrSmith42 Sep 19 '13 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. – Tom Au Sep 19 '13 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. – robosoul Sep 19 '13 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 ;) – ratchet freak Sep 19 '13 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 :) – robosoul Sep 19 '13 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. – haylem Sep 19 '13 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. – Stephen C Sep 19 '13 at 9:56
• this answer would be complete if you point out that this is exactly what version 1 is – ratchet freak Sep 19 '13 at 10:24