5

How can I shuffle an array's values in the most efficient manner possible?

Each element is just a string containing HTML.

Adam Lynch
  • 3,341
  • 5
  • 36
  • 66

4 Answers4

7

You have a few choices.

First, you could use the stupidely naïve sorter...

arr = arr.sort(function() {
    return Math.random() - .5
});

jsFiddle.

This is quick and dirty but often considered bad practice.

Further Reading.

The best way to randomly sort an Array is with the Fisher-Yates shuffle.

var newArr = [];

while (arr.length) {

   var randomIndex = Math.floor(Math.random() * arr.length),
       element = arr.splice(randomIndex, 1)

   newArr.push(element[0]);       

}

JSBin.

alex
  • 479,566
  • 201
  • 878
  • 984
  • How come you gave me a jsfiddle link for the one `"often considered bad practice"` and not the Fisher-Yates shuffle? – Adam Lynch Sep 05 '11 at 14:32
  • @Adam Just writing the Fisher Yates now and had to look it up :) – alex Sep 05 '11 at 14:34
  • It's ok. I'll use http://stackoverflow.com/questions/962802/is-it-correct-to-use-javascript-array-sort-method-for-shuffling/#answer-962890 – Adam Lynch Sep 05 '11 at 14:35
  • OpenDNS: `"Phishing Site Blocked Phishing is a fraudulent attempt to get you to provide personal information under false pretenses."` – Adam Lynch Sep 05 '11 at 14:50
  • let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/3182/discussion-between-adam-lynch-and-alex) – Adam Lynch Sep 05 '11 at 14:55
  • `splice` is extremely slow compared to `pop`. see [my answer](https://stackoverflow.com/a/65637626/633183) for details. – Mulan Jan 08 '21 at 23:55
3

Let me post my own answer just to encourage you NOT TO use random sort() method as it will produce not so random output.

As being said, Fisher-Yates shuffle is the most efficient algorithm for that purpose, and it can be easily implemented with the following ES6 code:

const src = [...'abcdefg'],

      shuffle = arr => arr.reduceRight((r,_,__,s) => 
        (r.push(s.splice(0|Math.random()*s.length,1)[0]), r),[])

console.log(JSON.stringify(shuffle(src)))
.as-console-wrapper {min-height:100%}
Yevhen Horbunkov
  • 14,965
  • 3
  • 20
  • 42
1

This is the one I use. It gives a random number to each element, sorts the array by those random numbers (moving the real values along) and then removes the random numbers again. It seems to be equally distributed, but I've not mathematically proven it yet.

arr = arr.map(function(v) {
    return [v, Math.random()];
}).sort(function(a, b) {
    return a[1] - b[1];
}).map(function(v) {
    return v[0];
});

http://jsfiddle.net/XQRFt/ - Test results (might be slow)

pimvdb
  • 151,816
  • 78
  • 307
  • 352
  • 1
    This relies on ECMAScript 5 `Array` methods, which rules out IE < 9. – Tim Down Sep 06 '11 at 00:06
  • @Tim Down: Yes, you're correct. In fact, those functions tend to be inefficient in terms of speed too. But personally I find it more readable. – pimvdb Sep 06 '11 at 05:44
0

This is my solution to shuffle an array:

    function shuffle(array) {
       var resultArray = new Array();
       for(i=0;i<array.length;i++) {
           var randomEle = Math.floor(Math.random()*array.length);
           resultArray.push(array[randomEle]);
           array.splice(randomEle,1);
       }
       resultArray = resultArray.concat(array);
       return resultArray;
    }

This is a shuffle contest to compare my method with the other 2

http://jsperf.com/shuffle-contest/2

Zahadum
  • 1
  • I've added the Fisher-Yates shuffle from @alex's [answer](http://stackoverflow.com/a/7309413/727074) to your jsPerf ['contest'](http://jsperf.com/shuffle-contest/3). It's the fastest – Adam Lynch May 10 '13 at 07:56
  • @AdamLynch : and I have added [mine](https://stackoverflow.com/a/56749849/11299053), so, let me [grab](https://jsperf.com/shuffle-contest/18) the prize for the modern, perfectly balanced (performance - conciseness) solution – Yevhen Horbunkov Jun 25 '19 at 14:26