【JavaScript】昇順ソート済み配列を最大値・最小値が交互になるように並べ替えるアルゴリズム

問題の概要

昇順にソート済みの整数配列が与えられたとします。ここで、組み込みの Array.prototype.sort() メソッドを使わずに、次のような規則で配列を並べ替えるJavaScript関数を作成することを考えます。

• 1番目の要素は最大値
• 2番目の要素は最小値
• 3番目の要素は2番目に大きい値
• 4番目の要素は2番目に小さい値
• 以降も同様に、大きい値と小さい値を交互に並べる

入出力の例

入力配列が次の場合を考えてみましょう。

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

このとき、期待される出力は次のとおりです。

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

最大値の 6、最小値の 1、次に大きい 5、次に小さい 2 というように、両端から交互に要素が並んでいることがわかります。

解決のアプローチ:ツーポインタ手法

この問題は、配列がすでに昇順でソートされているという性質を利用すると、非常に効率的に解くことができます。具体的には、配列の先頭を指す left ポインタと、末尾を指す right ポインタの2つを用意し、末尾(最大値側)と先頭(最小値側)から交互に要素を取り出して新しい配列に追加していきます。

この方法なら、配列を走査するのは1回だけで済むため、計算量は O(n) となり、非常に高速です。

コード例

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

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

const alternativeSort = (arr = []) => {
  const res = [];
  let left = 0;
  let right = arr.length - 1;
  while (res.length < arr.length) {
    res.push(arr[right]);
    if (left !== right) {
      res.push(arr[left]);
    }
    left++;
    right--;
  }
  return res;
};

console.log(alternativeSort(arr));

実行結果

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

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

コードの解説

処理の流れを順に見ていきましょう。

• 初期化: 結果を格納する配列 res を用意し、left を 0(先頭)、right を arr.length - 1(末尾)に設定します。
• ループ処理: res の要素数が元の配列と同じになるまでループを続けます。各ループでは、まず末尾側の要素 arr[right](大きい値)を追加します。
• 重複の回避: left と right が同じ位置を指している場合(要素数が奇数の場合の中央要素)、同じ値を2回追加しないように if 文でチェックしてから、先頭側の要素 arr[left](小さい値)を追加します。
• ポインタの移動: left を1つ進め、right を1つ戻して、次のペアへ移動します。

このように、ソート済み配列の性質を活かしたツーポインタ手法を使うことで、追加のソート処理を行うことなく、最大値と最小値が交互に並んだ配列を線形時間で生成できます。