【JavaScript】配列を交互に並べ替えるソート関数の実装方法

交互ソートとは？

JavaScriptで、数値の配列を唯一の引数として受け取る関数を作成することを考えます。この関数の目的は、配列内の要素を交互（alternating）な順序に並べ替えることです。

ここでいう「交互」とは、次のようなパターンを意味します。

たとえば、配列arrが4つの要素を持っているとすると、関数は配列の要素を次の条件を満たすようにシャッフルしなければなりません。

arr[0] < arr[1] > arr[2] < arr[3]

つまり、「小さい→大きい→小さい→大きい…」という波形のような並びを目指します。なお、1つの配列に対して条件を満たす答えは複数存在し得ますが、そのうちのどれか1つを返せば十分です。

入力例

const arr = [1, 2, 3, 4, 5, 6];

出力例（可能な解のひとつ）

const output = [ 3, 6, 2, 5, 1, 4 ];

サンプルコード

以下が実際の実装コードです。

const arr = [1, 2, 3, 4, 5, 6];
const alternateSort = (arr = []) => {
   arr.sort((a, b) => a - b);
   const N = arr.length;
   let mid = Math.floor(N/2);
   if(N % 2 !== 0){
      mid++;
   };
   const small = arr.splice(0, mid);
   const big = arr.splice(0,arr.length);
   for(let i = 0; i < N; i++){
      if(i % 2 === 0){
         arr[i] = small.pop()
      }else{
         arr[i] = big.pop()
      };
   };
};
alternateSort(arr);
console.log(arr);

実行結果

コンソールへの出力は次のようになります。

[ 3, 6, 2, 5, 1, 4 ]

コードの解説

このアルゴリズムは、次の3つのステップで構成されています。

1. 昇順にソートする： sort((a, b) => a - b) を使い、配列全体を昇順に並べ替えます。
2. 前半と後半に分割する： 配列長の半分を境に、小さい値のグループ（small）と大きい値のグループ（big）に分けます。要素数が奇数の場合は、中央の要素を小さい側のグループに含めます。
3. 交互に配置する： 偶数番目のインデックスには small の末尾から、奇数番目のインデックスには big の末尾から pop() で取り出した値を順に代入していきます。

smallグループのすべての値はbigグループのどの値よりも小さいため、偶数位置の要素は必ず隣接する奇数位置の要素より小さくなります。この性質により、arr[0] < arr[1] > arr[2] < … という交互パターンが自動的に保証される仕組みです。

計算量について

処理時間はソート部分が支配的となるため、時間計算量は O(n log n) となります。分割と再配置の処理はそれぞれ線形時間 O(n) で完了し、一時的な配列を使用するため空間計算量は O(n) です。