Here is a really funny story
I imagine how that happened:
Dude1: “Dude, how do I randomly shuffle an array?”
Dude2: “Easy: just sort it in a random order.”
Dude1: “Awesome idea! Here I go: array.Sort(randomOrder)”.
Instead of sorting the array in a random order, the dude sorted it using a random comparer. Which resulted in a non-uniform shuffle with distribution that depends on the sorting algorithm.
While this shuffle algorithm http://en.wikipedia.org/wiki/Fisher-Yates_shuffle remains the fastest, simplest and safest, sorting by a random key is not a wrong approach. But if we choose it, we need to be very cautious. We need to make sure the random keys don’t change during sorting, otherwise it may be same as using a random comparer. Check this out:
var list = Enumerable.Range(1, 10); Random rand = new Random(); var sorted = list.OrderBy(i => rand.NextDouble());
The code looks suspiciously similar to the wrong implementation. But the parameter of Enumerable.OrderBy() is not a comparer, but rather a key selector. So this code should result in a uniform shuffle (assuming Random.NextDouble() is uniform). But imagine what happens if the OrderedEnumerable enumerator calls the key selector function each time it compares two elements. Then our random key selector becomes equivalent to the random comparer and the result is not uniform. I attempted to figure out how OrderedEnumerable actually works using Reflector, but I gave up. Instead I just ran some tests to check how many times the key selector gets called, and it appeared that it’s called only once for each element. But I would still use the Knuth – Fisher – Yates, of course.
Anagram of the day “uniform shuffle” = “snuff life humor”