JavaScriptで配列をシャッフルするには？sort()メソッドの注意点とFisher-Yates法による実装例

JavaScriptで配列をシャッフルしたい場合、Array.sort()メソッドを使う方法がよく知られています。しかし、実はこの方法には落とし穴があります。ここでは、sort()を使ったシャッフルの問題点と、より正確なシャッフルを実現できる「Fisher-Yates（フィッシャー・イェーツ）アルゴリズム」の実装例をわかりやすく紹介します。

sort()メソッドでシャッフルする際の注意点

Math.random()を比較関数としてsort()に渡す方法はコードが短く手軽ですが、結果の並び順に偏りが生じることが知られています。これは、ソートアルゴリズムの内部動作と乱数の組み合わせが、統計的に均等なランダム性を保証しないためです。そのため、厳密なランダム性が求められる場面では別の手法を選ぶべきです。

おすすめの方法：Fisher-Yatesアルゴリズム

偏りのないシャッフルを実現するには、以下のようなFisher-Yatesアルゴリズムを使用するのが定番です。配列の末尾から先頭に向かって走査しながら、各要素を残りの未確定要素の中からランダムに選んだ要素と入れ替えていきます。

実装例

function shuffleDisplay(arr) {
    var tmp, current;

    // 配列の長さを取得
    var top = arr.length;

    if(top) while(--top) {
        current = Math.floor(Math.random() * (top + 1));
        tmp = arr[current];
        arr[current] = arr[top];
        arr[top] = tmp;
    }
    return arr;
}

コードの解説

この関数は次の手順で動作します。

• 引数として受け取った配列の長さを変数topに格納します。
• whileループにより、末尾の要素から順に処理を行い、全要素の確定が完了した時点で終了します。
• 各ループ内では、Math.floor(Math.random() * (top + 1))によって、0からtopまでの範囲でランダムなインデックスcurrentを選び出します。
• 選ばれた要素arr[current]と末尾側の要素arr[top]を、一時変数tmpを使って交換します。
• すべての入れ替えが完了したら、シャッフル済みの配列を返します。

このアルゴリズムの計算量はO(n)と非常に効率的で、すべての並び順が等しい確率で出現することが数学的に保証されています。そのため、実務や本番環境でも安心して利用できる、信頼性の高いシャッフル手法といえます。