Categories
arrays javascript random shuffle

How to randomize (shuffle) a JavaScript array?

1774

I have an array like this:

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

How can I randomize / shuffle it?

11

  • 8

    Just throwing this here that you can visualize how random a shuffle function actually is with this visualizer Mike Bostock made: bost.ocks.org/mike/shuffle/compare.html

    – aug

    Dec 10, 2014 at 19:42

  • 6

    @Blazemonger jsPref is dead. Can you just post here which is the fastest?

    – eozzy

    Sep 28, 2016 at 1:06

  • 26

    How about this? arr1.sort(() => (Math.random() > .5) ? 1 : -1);

    – yuval.bl

    Sep 26, 2018 at 17:18


  • 5

    a short answer would be a.sort(() => Math.random() - 0.5)

    – SaboSuke

    Sep 3, 2021 at 18:52


  • 3

    @TheVee see few lines above, on the same spec: “The sort order is implementation-defined if …If comparefn is not undefined and is not a consistent comparison function for the elements of items”

    – yuval.bl

    Nov 11, 2021 at 16:12

2181

The de-facto unbiased shuffle algorithm is the Fisher-Yates (aka 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.

7

  • 19

    The above answer skips element 0, the condition should be i-- not --i. Also, the test if (i==0)... is superfluous since if i == 0 the while loop will never be entered. The call to Math.floor can be done faster using ...| 0. Either tempi or tempj can be removed and the value be directly assigned to myArray[i] or j as appropriate.

    – RobG

    Jun 8, 2011 at 7:21


  • 61

    @RobG the implementation above is functionally correct. In the Fisher-Yates algorithm, the loop isn’t meant to run for the first element in the array. Check out wikipedia where there are other implementations that also skip the first element. Also check out this article which talks about why it is important for the loop not to run for the first element.

    – theon

    Jul 20, 2012 at 12:57


  • 1

    Be sure to transpile if you’re going to do destructuring assignments in a busy loop — allocating objects is expensive.

    – ggorlen

    Jul 25, 2021 at 22:18

  • @ggorlen What do you mean by transpiling in this context? Can you give us an example or further explanation?

    – nkhil

    Oct 4, 2021 at 16:12

  • 1

    I’m a bit surprised that this is the top answer. There are actually a lot of things wrong… Improper scoping, neglecting to simply use a for loop, incorrectly using != with !==, the infinite loop if passed an empty array, and the modification and return of a parameter.

    – Sam

    Mar 14 at 3:18


1050

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]];
    }
}

9

288

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.

12

  • 13

    Very nice. This is the Schwartzian transform in js.

    Jun 29, 2018 at 10:43

  • 11

    This is the best answer here (for short arrays) for a number of reasons. to me, it’s really useful because I’m using react in 2021 which works best with a functional approach like this.

    Sep 1, 2021 at 13:43

  • 1

    Think about the compexity again if you have to map 2 times it goes over the elements N two times already and that is not considering the quick sort complexity of JS’s .sort algorithm

    – Ilja KO

    Mar 23 at 9:51

  • @IljaKO 2N is still O(N), which is less than the time complexity of O(N log N)

    Apr 24 at 1:40

  • 1

    @IljaKO – O(2N + 2(N log N)) simplifies to O(N log N), so this is truly O(N log N). Big O notation is all about the largest scaling factor. We remove constants because they don’t scale with input size, and simplify to the largest single scaling factor. Big O notation is deliberately NOT all about the details.

    Jun 10 at 11:51