Advanced Puzzlers - Java Puzzlers: Traps, Pitfalls, and Corner Cases - page 295

Why does the graph have this shape? We don't know all the details but we can offer some intuition.
Let's restrict our attention to the array's first element. After the first iteration of the loop, it has the
correct expected value of ( n - 1) / 2. In the second iteration, however, there is 1 chance in n that the
random number generator will return 0 and the value in the first element will be replaced by 1 or 0.
In other words, the second iteration systematically reduces the expected value of the first element.
In the third iteration, there's a further 1 chance in n that the first element is replaced by 2, 1, or 0,
and so on. For the first n / 2 iterations of the loop, the expected value of the first element decreases.
For the second n / 2 iterations, it increases but never catches up to its fair value. Note that the last
element in the array is guaranteed to have the correct expected value, as the last step in the
execution of the method is to select it at random from all the elements in the array.
OK, so our shuffle method is broken. How do we fix it? Use the shuffle method provided by the
library:
import java.util.*;
public class Shuffle {
public static void shuffle(Object[] a) {
Collections.shuffle(Arrays.asList(a));
}
}
Whenever the libraries provide a method that does what you need, use it [EJ Item 30].
Generally speaking, the libraries provides high-quality solutions requiring a minimum of effort on
your part.
On the other hand, after you suffered through all that math, it seems unfair not to tell you how to fix
the broken shuffle method. The fix is actually quite straightforward. In the body of the loop, swap
the current element with an element selected at random from the portion of the array starting at the
current element and extending to the end of the array. Do not touch an element once you've
swapped a value into it. This is essentially the algorithm that is used by the library method:
public static void shuffle(Object[] a) {
for (int i = 0; i < a.length; i++)
swap(a, i, i + rnd.nextInt(a.length - i));
}