この記事は、ラクスパートナーズ AdventCalendar 2025の11日目の記事です。
（個人で25日連続投稿にチャレンジ中のカレンダーになります）
今回は、Fisher-Yates shuffl（フィッシャー イェーツのシャッフル）アルゴリズムについて解説したいと思います。
フィッシャー–イェーツのシャッフル (英: Fisher–Yates shuffle) は、有限集合からランダムな順列を生成するアルゴリズムである。言い換えると、有限列をランダムな別の（シャッフルされた）順序の有限列に並べ直す方法である。
難しい言葉で書かれていますが、
「特定の配列の中からランダムで値を選択して並べ替え、新たな配列を作る」
というアルゴリズムがFisher-Yates shufflです。
JavaScriptにおいては、以下のようにMath.random()とMath.floor()を組み合わせて実現します。
Math.random()は0以上1未満の浮動小数点数をランダムで返す関数で、
Math.floor()は指定した値の小数点以下を切り捨てる関数です。
const fisherYatesShuffl = (array) => {
// 配列の数の分だけ処理を実行
for (let i = array.length - 1; i > 0; i--) {
// ランダムなindex番号を作成
const j = Math.floor(Math.random() * (i + 1));
// 元の配列のi番目とランダムに選んだj番目の要素の順序を入れ替え
[array[i], array[j]] = [array[j], array[i]];
}
// 入れ替え後の配列を返す
return array;
}
// 1~100までの数値が入った配列を生成
const numbers = Array.from({ length: 100 }, (_, i) => i + 1);
fisherYatesShuffl(numbers)
上記の例では、1~100の数値をランダムな順番に入れ替えています。
Fisher-Yates shufflアルゴリズムのメリット
メモリ使用量が少ない（追加メモリがほとんどない）
Fisher-Yates shufflアルゴリズムは元の配列を参考にその場でシャッフルを行うだけのため、メモリ使用量が少ない（追加メモリがほとんどない）とされています。
偏りが起きない
「この値だけよく先頭に出てくる」といったような偏りが起きず、全ての要素が同じ確率で出ることが保証されています。
計算が高速
計算にかかる時間がO(n)のため高速とされています。
O記法は、計算にかかる時間とデータ量を表現した記法です。
以下のような種類があります。
- O(1)：データ量に関係なく、計算を1回だけ行う
- O(n)：データ量（n）が増えた分だけ、計算量も比例する
- O(n^2)：データ量(n)に対して、計算量が n*n (nを2乗した)分増えていく
- O(log n)：データ量(n)に対して、計算量が常に半分になる
O(n^2)になる処理はかなりの計算量になるため、プログラムにおいては避けるべきだと言われています。
Fisher-Yates shufflアルゴリズムは計算量がO(n)、つまり
「データ量の分だけ計算量が増えていく」
ため、処理のスピードが高速となっています。
以上となります。
「特定の配列をランダムで並べ替える」という実装は意外と多かったりしますし、他のプログラミング言語を扱う際にも同じ考え方ができたりします。
業務ではどうしてもフレームワークの特定の機能の使い方を覚えるのに目が行きがちですが、こういったアルゴリズムもぜひ覚えていきたいですね。
ここまで読んでいただき、ありがとうございました。
参考
非常にわかりやすかったです！
ありがとうございました🙇♂️