How to randomize (shuffle) a JavaScript array? – Dev

The best answers to the question “How to randomize (shuffle) a JavaScript array?” in the category Dev.

QUESTION:

I have an array like this:

var arr1 = ["a", "b", "c", "d"];

How can I randomize / shuffle it?

ANSWER:

Here’s a JavaScript implementation of the Durstenfeld shuffle, an optimized version of Fisher-Yates:

/* Randomize array in-place using Durstenfeld shuffle algorithm */
function shuffleArray(array) {
    for (var i = array.length - 1; i > 0; i--) {
        var j = Math.floor(Math.random() * (i + 1));
        var temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

It picks a random element for each original array element, and excludes it from the next draw, like picking randomly from a deck of cards.

This clever exclusion swaps the picked element with the current one, then picks the next random element from the remainder, looping backwards for optimal efficiency, ensuring the random pick is simplified (it can always start at 0), and thereby skipping the final element.

Algorithm runtime is O(n). Note that the shuffle is done in-place so if you don’t want to modify the original array, first make a copy of it with .slice(0).


EDIT: Updating to ES6 / ECMAScript 2015

The new ES6 allows us to assign two variables at once. This is especially handy when we want to swap the values of two variables, as we can do it in one line of code. Here is a shorter form of the same function, using this feature.

function shuffleArray(array) {
    for (let i = array.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [array[i], array[j]] = [array[j], array[i]];
    }
}

ANSWER:

The de-facto unbiased shuffle algorithm is the Fisher-Yates (aka Knuth) Shuffle.

See https://github.com/coolaj86/knuth-shuffle

You can see a great visualization here (and the original post linked to this)

function shuffle(array) {
  let currentIndex = array.length,  randomIndex;

  // While there remain elements to shuffle...
  while (currentIndex != 0) {

    // Pick a remaining element...
    randomIndex = Math.floor(Math.random() * currentIndex);
    currentIndex--;

    // And swap it with the current element.
    [array[currentIndex], array[randomIndex]] = [
      array[randomIndex], array[currentIndex]];
  }

  return array;
}

// Used like so
var arr = [2, 11, 37, 42];
shuffle(arr);
console.log(arr);

Some more info about the algorithm used.

ANSWER:

Warning!
The use of this algorithm is not recommended, because it is inefficient and strongly biased; see comments. It is being left here for future reference, because the idea is not that rare.

[1,2,3,4,5,6].sort( () => .5 - Math.random() );

This https://javascript.info/array-methods#shuffle-an-array tutorial explains the differences straightforwardly.

ANSWER:

You can do it easily with map and sort:

let unshuffled = ['hello', 'a', 't', 'q', 1, 2, 3, {cats: true}]

let shuffled = unshuffled
  .map((value) => ({ value, sort: Math.random() }))
  .sort((a, b) => a.sort - b.sort)
  .map(({ value }) => value)
  1. We put each element in the array in an object, and give it a random sort key
  2. We sort using the random key
  3. We unmap to get the original objects

You can shuffle polymorphic arrays, and the sort is as random as Math.random, which is good enough for most purposes.

Since the elements are sorted against consistent keys that are not regenerated each iteration, and each comparison pulls from the same distribution, any non-randomness in the distribution of Math.random is canceled out.

Speed

Time complexity is O(N log N), same as quick sort. Space complexity is O(N). This is not as efficient as a Fischer Yates shuffle but, in my opinion, the code is significantly shorter and more functional. If you have a large array you should certainly use Fischer Yates. If you have a small array with a few hundred items, you might do this.