TL;DR: If you want something quick and simple, yourArray.sort(() => Math.random() - 0.5)
will do the job. But for better performance on larger arrays, check out the Fisher-Yates shuffle (code below).
Pick a card, any card…
Other than shuffling a deck of cards, there are many reasons why you might want to shuffle an array into a random order. Random options on a survey, random users in a group, random clues for a quiz. And you might want to show an array of random objects, random numbers, or random strings.
For this example, I’ll be shuffling a deck of cards, with an array of card objects, but the examples will work with any array.
Here’s my deckOfCards
array.
var deckOfCards = [];
var suits = ["clubs", "diamonds", "hearts", "spades"];
var ranks = [2,3,4,5,6,7,8,9,10,"J","Q","K","A"];
for (var i=0; i<suits.length; i++) {
for (var j=0;j<ranks.length;j++) {
deckOfCards.push({'rank': ranks[j], 'suit': suits[i]});
}
}
console.log(deckOfCards);
// [
// {"rank":2,"suit":"clubs"},
// {"rank":3,"suit":"clubs"},
// {"rank":4,"suit":"clubs"},
// {"rank":5,"suit":"clubs"},
// {"rank":6,"suit":"clubs"},
// {"rank":7,"suit":"clubs"},
// {"rank":8,"suit":"clubs"},
// {"rank":9,"suit":"clubs"},
// {"rank":10,"suit":"clubs"},
// {"rank":"J","suit":"clubs"},
// {"rank":"Q","suit":"clubs"},
// {"rank":"K","suit":"clubs"},
// {"rank":"A","suit":"clubs"},
// {"rank":2,"suit":"diamonds"},
// // ...
// ];
I picked this array, because it’s reasonably large, so I can check the performance of the two JavaScript methods I use for randomly shuffling an array.
Array.sort() for shuffling an array
The first option I went for was Array.sort()
- because I’m sorting an array so it naturally springs to mind!
let shuffled = deckOfCards.sort(() => Math.random() - 0.5);
What's going on here?
We can use Array.sort()
to sort an array in JavaScript, but instead of sorting by string, object property, or number, we just want to sort randomly.
So for each item, we need to randomly return 1, -1 or 0, to randomly sort the array. Hello Math.random()
!
Instead of numbers between 0 and 1, we want numbers between less than 0 (to sort the item before) or more than 0 (to sort it after) or 0 to stay the same. -0.5 gets us the results we need, because the random numbers will be from -0.5 to 0.5.
This one looks pretty simple and can be done in one line of code, which is always mentally pleasing.
But how does it perform?
console.time('sort');
deckOfCards.sort(() => Math.random() - 0.5);
console.timeEnd('sort');
I ran this a few times to get an average.
sort: 0.0458984375 ms
sort: 0.045166015625 ms
sort: 0.06005859375 ms
sort: 0.050048828125 ms
sort: 0.052978515625 ms
Well, it shuffles our deck of cards in around 0.05ms, which is pretty quick. But can we do better?
The Fisher-Yates shuffle
I got most of the code ideas for this from Mike Bostock and his shuffle blog post - which is worth checking out for the super cool shuffle visualizations.
I'd been using the code in my shuffleArray
function to shuffle quiz questions for a while in one of my projects. I must have got it from somewhere - as I'm pretty sure I didn't come up with a Fisher-Yates shuffle all by myself!
Since looking into it some more, it turns out the popular JavaScript library Lodash uses the Fisher-Yates shuffle too, so there must be something to it!
Here's the version I'm using:
function shuffleArray(array) {
let length = array.length;
let shuffle = array.slice(); // copy of array
// loop over the array
for (let i = length - 1; i > 0; i -= 1) {
let random = Math.floor(Math.random() * (i + 1)); // random card position
let current = shuffle[i]; // current card
// swap the random card and the current card
shuffle[i] = shuffle[random]; // move the random card to the current position
shuffle[random] = current; // put the current card in the random position
}
return shuffle; // return shuffled array
};
The comments hopefully explain what's going on, but essentially we loop through the entire deck switching each card randomly. Since cards get switched further up and down the deck (with the random
card position), the same card can get switched around multiple times.
So how does the shuffleArray
function perform?
console.time('shuffleArray');
shuffleArray(deckOfCards);
console.timeEnd('shuffleArray');
Again, I ran this a few times to get an average.
shuffleArray: 0.059814453125 ms
shuffleArray: 0.045166015625 ms
shuffleArray: 0.06884765625 ms
shuffleArray: 0.06103515625 ms
shuffleArray: 0.072021484375 ms
Maybe averaging slightly higher at 0.06ms, but what's 0.01ms between friends?
For short arrays (like our 52-card deck) Array.sort()
seems to win the race. But once I increased the array to over 200 items, the Fisher-Yates shuffleArray
function became the quicker of the two.
sort: 0.152099609375 ms
shuffleArray: 0.091796875 ms
And with over 400 items, that speed difference increases even more!
sort: 0.327880859375 ms
shuffleArray: 0.130859375 ms
So for larger arrays, the Fisher-Yates shuffle seems to perform much better.
I'm not sure exactly why the Fisher-Yates shuffle is more efficient, but it makes me lean towards the shuffleArray
function for anything non-trivial.