Ben Nadel
On User Experience (UX) Design, JavaScript, ColdFusion, Node.js, Life, and Love.
I am the chief technical officer at InVision App, Inc - a prototyping and collaboration platform for designers, built by designers. I also rock out in JavaScript and ColdFusion 24x7.
Meanwhile on Twitter
Loading latest tweet...
Ben Nadel at CFUNITED 2009 (Lansdowne, VA) with:

Implementing Java's Collections.Shuffle() In JavaScript

By Ben Nadel on

When I'm working with ColdFusion, and I need to shuffle an array of items, my default move is to pass the array down into the Java layer where I can leverage the Collections class. There, the shuffle() method makes sorting an array a simple task. The other day, I needed to shuffle a JavaScript array in the browser; so, I wanted to see if I could implement the same shuffle() algorithm in JavaScript. As it turns out, it's not too complicated.

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.

  • <!doctype html>
  • <html>
  • <head>
  • <meta charset="utf-8" />
  •  
  • <title>
  • Implementing Collections.Shuffle() In JavaScript
  • </title>
  • </head>
  • <body>
  •  
  • <h1>
  • Implementing Collections.Shuffle() In JavaScript
  • </h1>
  •  
  • <!-- Load scripts. -->
  • <script type="text/javascript">
  •  
  • // Define our collection object with exposed methods.
  • var collections = (function() {
  •  
  • // I generate a random integer between the min and max, both of which are
  • // inclusive in the range. If the "min" argument is omitted, the range is
  • // assumed to be zero-to-max.
  • function randRange( min, max ) {
  •  
  • // If only one argument, assumed to be Max.
  • if ( arguments.length === 1 ) {
  •  
  • max = arguments[ 0 ];
  • min = 0;
  •  
  • }
  •  
  • var range = ( max - min + 1 );
  •  
  • var offset = Math.floor( range * Math.random() );
  •  
  • return( min + offset );
  •  
  • }
  •  
  •  
  • // I shuffle the collection using the given rand-range implementation. If
  • // no implementation is provided, the default implementation is used.
  • // --
  • // NOTE: Uses the Fisher-Yates shuffle algorithm.
  • function shuffle( collection, randRangeImplementation ) {
  •  
  • // If a rand-range implementation is not provided, use the default.
  • if ( ! randRangeImplementation ) {
  •  
  • randRangeImplementation = randRange;
  •  
  • }
  •  
  • var length = collection.length;
  • var i = length;
  •  
  • // Loop backwards through the list, randomly swapping indices.
  • while( --i ) {
  •  
  • var j = randRangeImplementation( i );
  •  
  • if ( i !== j ) {
  •  
  • swap( collection, i, j );
  •  
  • }
  •  
  • }
  •  
  • return( collection );
  •  
  • }
  •  
  •  
  • // I swap the value at the given indices in the given collection.
  • function swap( collection, i, j ) {
  •  
  • var tempValue = collection[ i ];
  •  
  • collection[ i ] = collection[ j ];
  • collection[ j ] = tempValue;
  •  
  • }
  •  
  •  
  • // Return the public API.
  • return({
  • shuffle: shuffle
  • });
  •  
  • })();
  •  
  •  
  • // ------------------------------------------------------- //
  • // ------------------------------------------------------- //
  •  
  •  
  • // Let's try it out - build up a collection of numbers, shuffle, then output.
  • var numbers = [];
  •  
  • for ( var i = 1 ; i < 20 ; i++ ) {
  •  
  • numbers.push( i );
  •  
  • }
  •  
  • collections.shuffle( numbers );
  •  
  • console.log( numbers.join( ", " ) );
  •  
  • </script>
  •  
  • </body>
  • </html>

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

Note that this approach, just as with Java's Collections.shuffle() method, shuffles the array "in place." Meaning, it doesn't return a new, shuffled copy of the array but, rather, the original array with updated values. This is different than several of the "functional" JavaScript libraries that return new arrays as the shuffled result.

To be honest, I didn't realize that the various functional JavaScript libraries (such as LoDash and Underscore) already had shuffle() methods until I was already writing this post. That said, it was interesting to learn more about this algorithm. Both in JavaScript and Java.




Reader Comments

@Bob,

That's an interesting approach. I'll have to read up the discussion a bit more. Thanks!

Reply to this Comment

Hi Ben,
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.

Reply to this Comment

@Steven,

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!

Reply to this Comment

@Federico,

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!

Reply to this Comment

@Federico

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.

Reply to this Comment

Post A Comment

You — Get Out Of My Dreams, Get Into My Comments
Live in the Now
Oops!
Comment Etiquette: Please do not post spam. Please keep the comments on-topic. Please do not post unrelated questions or large chunks of code. And, above all, please be nice to each other - we're trying to have a good conversation here.