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

  • 13
    いいね
  • 3
    コメント
この記事は最終更新日から1年以上が経過しています。

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

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は偏る