JavaScriptでバタフライシャッフルを実装する方法をわかりやすく解説

バタフライシャッフルとは

JavaScriptにおける「バタフライシャッフルされた配列」とは、数値の配列を、中央に近づくほど値が減少し、末尾に近づくほど値が増加するように並べ替えたものです。この場合、最も大きな数値が配列の先頭に配置されます。

別のバリエーションとして、中央に向かって増加し、末尾に向かって減少するパターンも存在します。この場合は逆に、最も小さい数値が先頭に配置されます。

数学のバックグラウンドをお持ちの方なら、正規分布（ガウス分布）の形状に少し似ていると感じられるかもしれません。山が中央にあり、両端に向かって裾広くなるイメージです。

具体例

たとえば、次のような配列があるとします。

const arr = [8, 2, 6, 3, 9, 1, 4, 5, 0, 7];

これにバタフライシャッフルを適用すると、出力は次のようになります。

[9, 7, 5, 3, 1, 0, 2, 4, 6, 8]

ご覧のとおり、最大値とその次に大きい数値が両端に配置され、最小値が中央に来ています。

もう一つのパターンとして、次のような出力も考えられます。

[0, 2, 4, 6, 8, 9, 7, 5, 3, 1]

実装する関数の仕様

今回作成する関数は、第1引数に数値の配列、第2引数に文字列を受け取ります。文字列には 'asc' または 'des' のいずれかを指定します。

• 'des' が指定された場合：降順から昇順へ向かう並び（大きい値が端、小さい値が中央）でシャッフルします。

• 'asc' が指定された場合：昇順から降順へ向かう並び（小さい値が端、大きい値が中央）でシャッフルします。

アプローチ（実装の方針）

• まず、文字列が 'asc' なら配列を昇順に、そうでなければ降順にソートします。たとえば 'asc' で呼び出された場合、配列はこのようになります。

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

• 次に、この配列を隣り合う要素が交互に別々の配列へ振り分けられるように2つに分割します。片方の配列には push() で要素を追加し、もう片方には unshift() で先頭に追加することで、手動で反転処理を書かなくても、自動的に逆向きの並びを持つ配列が得られます。

この時点でできる2つの配列は次のようになります。

[0, 2, 4, 6, 8] [9, 7, 5, 3, 1]

• 最後のステップは、これら2つの配列を連結することです。これで目的の配列が完成します。以上の処理をコードにまとめると、次のようになります。

コード例

const array = [8, 2, 6, 3, 9, 1, 4, 5, 0, 7];

const butterflyShuffle = (array, order = 'asc') => {
   // 元の配列を変更しないよう、コピーを作成する
   const arr = array.slice();
   // 引数に応じて昇順または降順にソートする
   arr.sort((a, b) => order === 'asc' ? a - b : b - a);
   const first = [], second = [];
   // 配列の長さが偶数かどうかで、最後の要素がどちらの配列に入るかが決まる
   // 偶数なら最後の要素は second へ、奇数なら first へ振り分けられる
   const isEven = arr.length % 2 === 0;
   for (let i = 0; i < arr.length; i++){
      if (i % 2 === 0){
         isEven ? first.push(arr[i]) : first.unshift(arr[i]);
         continue;
      };
      isEven ? second.unshift(arr[i]) : second.push(arr[i]);
   };
   return isEven ? second.concat(first) : first.concat(second);
};
console.log(butterflyShuffle(array));
console.log(butterflyShuffle(array, 'des'));

出力結果

コンソールには次のように出力されます。

[
    9, 7, 5, 3, 1,
    0, 2, 4, 6, 8
]
[
    0, 2, 4, 6, 8,
    9, 7, 5, 3, 1
]

まとめ

バタフライシャッフルは、「ソート」→「交互に分割」→「連結」というシンプルな3ステップで実装できます。ポイントは push() と unshift() を使い分けることで、反転処理を明示的に書かずに済ませている点です。また、slice() で元の配列のコピーを作成しているため、入力配列を破壊しない安全な設計になっています。