Fisher-Yates Shuffle
ロナルド・フィッシャーさんおよびフランク・イェーツさんが考案したシャフルのアルゴリズムです。
アルゴリズムのイメージ
くじ引きの箱の中から1つずつくじを引いて並べてシャッフルするイメージです。
「取り出す範囲(くじ箱の中)」と「結果の範囲(くじ箱の外)」の2つに分けて考えます。
手順
- 取り出す範囲(箱の中)から取り出す値をランダムに1つ決定する。
- 末尾の値と交換する。末尾を結果の範囲(くじ箱の外)とする。
- くじ箱の外が新しくできたので、取り出す範囲(くじ箱の中)を1つ前に狭める。
- 上記3つの処理を先頭の値がくじ箱の外になるまで繰り返す。
- 値が不規則に並んでかえってくる
おわり
//ソートされた配列
a = [1,2,3,4,5,6,7,8,9];
//取り出す範囲(箱の中)を末尾から狭める繰り返し
for(i = a.length -1;i>0;i--){
//乱数生成を使ってランダムに取り出す値を決める
r = Math.floor(Math.random()*(i+1));
//取り出した値と箱の外の先頭の値を交換する
tmp = a[i];
a[i] = a[r];
a[r] = tmp;
}
//結果を表示
console.log(a);