After a little bit of Googling, I discovered that the Collections.shuffle() method uses the "Fisher-Yates" algorithm. This approach loops backwards over the array and swaps the current element with another randomly-selected element in the array. In the Java class, you can pass-in your own randomization method; or, you can use the internal one. I tried to replicate this feature by allowing an optional argument in the shuffle() method.
As you can see, we're building up an array of numbers, one through twenty, shuffling them, and then logging them to the console. When I run the page a few times, I get the following results:
9, 19, 4, 2, 5, 13, 7, 17, 12, 1, 8, 11, 18, 6, 16, 3, 15, 14, 10
19, 5, 13, 7, 4, 17, 3, 16, 11, 1, 9, 12, 15, 6, 2, 14, 18, 8, 10
3, 11, 8, 4, 5, 9, 7, 19, 18, 13, 15, 6, 2, 1, 17, 14, 16, 12, 10
19, 11, 4, 12, 9, 7, 14, 10, 17, 6, 16, 3, 15, 5, 13, 8, 18, 1, 2
18, 10, 14, 7, 19, 3, 1, 4, 16, 15, 2, 9, 5, 13, 11, 12, 8, 17, 6
7, 6, 3, 16, 15, 8, 2, 1, 5, 17, 14, 4, 19, 18, 12, 11, 9, 10, 13
Want to use code from this post? Check out the license.
Here is a post to a discussion on Fisher-Yates vs the above bubble sort approach.
That's an interesting approach. I'll have to read up the discussion a bit more. Thanks!
Mike Bostock did a pretty good explanation of the various approaches to JS shuffling here, with Fisher-Yates taking pride of place at the end:
I found myself using it often enough to turn it into a gist and forget about it. Like you said, the best part has to be getting the original array back rather than a copy.
given that the naive Array.sort based solution mentioned by Bob is maybe the worst one, it really seem like the Fisher-Yates rules. I tried to speed it up, obtaining good results [http://www.jmvc.org/test_arrayShuffle].
I even tried to test the three solutions suggested by Steven, but time are comparable to the Array.sort based or even worst.
Thank You for the cue.
Yooo, that page was awesome. I love the animations and it does a great job of illustrating why some of the approaches are slower. Great find!
Great exploration. I had to look up what the "~~" was doing. Bit-wise operations. Really interesting to see the variations, and how fast some of these things execute on such a large array!
When valuing one approach over another I think it is important state the criteria. At times I've gone too far down the road of optimizing to later regret lack of clarity and simplicity of the code. I suspect for most it would be a rare occasion that required the need to shuffle 1000000 items. I think simple approach has merit for being simple, not for being optimized. But it might not be the best approach for all situations.
You`re absolutely right. I just wanted to share some digging