JavaScript

JavaScriptで配列をシャッフルする方法

More than 3 years have passed since last update.

調べていて多かったもの。


Array.prototype.sort()を用いる方法

例:

array.sort(function() { Math.random() - .5; });


  • 最小計算量は$O(n)$だが最悪計算量は$O(n^2)$である

  • シャッフルの結果に偏りが見られる



Fisher–Yatesアルゴリズムを用いる方法

例:

for(var i = array.length - 1; i > 0; i--){

var r = Math.floor(Math.random() * (i + 1));
var tmp = array[i];
array[i] = array[r];
array[r] = tmp;
}


  • 計算量は常に$O(n)$である

  • シャッフル結果にほとんど偏りが見られない



参考

Array#sort実装のshuffleは偏る