JavaScriptで配列を波状（ジグザグ）パターンに並べ替える方法

問題

数値の配列 arr を唯一の引数として受け取るJavaScript関数を作成します。この関数は、並べ替え後の配列の要素が次のパターンに従うように並べ替える必要があります。

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

このような並べ順は「波状ソート」や「ジグザグソート」と呼ばれることもあります。偶数番目のインデックスの要素は隣接する要素より小さく、奇数番目のインデックスの要素は隣接する要素より大きくなるように配置するのがポイントです。

例として、関数への入力が次の場合を考えてみましょう。

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

このとき、出力は次のようになります（波状パターンを満たす答えは複数存在する場合があります）。

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

この結果は 1 < 6 > 1 < 5 > 1 < 4 となっており、条件を正しく満たしていることがわかります。

解決のアプローチ

この問題は、次の手順で効率的に解くことができます。

1. まず、配列を昇順に並べ替えます。
2. 並べ替えた配列を、小さい値を含む前半部分と、大きい値を含む後半部分の2つに分割します（要素数が奇数の場合は、前半を1つ多くします）。
3. 元の配列に対して、偶数インデックスには前半部分を後ろから、奇数インデックスには後半部分を後ろから順に要素を埋めていきます。

こうすることで、比較的大きな値と小さな値が交互に配置され、自然に波状パターンが実現されます。計算量は並べ替えの O(n log n) が支配的となり、非常に効率的です。

コード例

この考え方を実装したコードは次のとおりです。

const arr = [1, 5, 1, 1, 6, 4];
const unevenSort = (arr = []) => {
   arr.sort((a, b) => a - b);
   let mid = Math.floor(arr.length / 2);
   if(arr.length % 2 === 1){
      mid += 1;
   };
   let even = arr.slice(0, mid);
   let odd = arr.slice(mid);
   for(let i = 0; i < arr.length; i++){
      if(i % 2 === 0){
         arr[i] = even.pop();
      }else{
         arr[i] = odd.pop();
      };
   };
};
unevenSort(arr);
console.log(arr);

出力

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

[ 1, 6, 1, 5, 1, 4 ]