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

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

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