JavaScriptで3種類の要素のみを含む配列を線形時間O(n)でソートする方法

次のような、-1、0、1 の3種類の値だけが任意の頻度で含まれる数値配列を考えてみましょう。

const arr = [1, 1, 0, -1, 1, 0, -1, 1, 0, 0, 1];

このような配列を引数として受け取り、余分な配列を使わずに（インプレースで）ソートするJavaScript関数を作成します。

ただし、重要な条件が1つあります。それは、関数が線形時間 O(n) で動作すること、つまり配列をたった1回の走査でソートを完了させなければならないという点です。

解決のポイント：3つのポインタを使った領域分割

この問題は、有名な「オランダ国旗問題（Dutch National Flag Problem）」と同じ考え方で解くことができます。3つのポインタを使い、配列を次の3つの領域へ分割しながら並べ替えていきます。

• left：この位置より左側は、すべて -1 で確定済み
• middle：現在調査中の要素の位置
• right：この位置より右側は、すべて 1 で確定済み

middle が指す要素の値に応じて、次のように処理を振り分けます。

• arr[middle] が -1 の場合：left と middle の要素を交換し、両方のポインタを1つ進めます。
• arr[middle] が 0 の場合：その位置はすでに正しいため、middle だけを1つ進めます。
• arr[middle] が 1 の場合：right と middle の要素を交換し、right だけを1つ減らします。ここで middle を進めないのがポイントです。右側から入れ替わってきた要素はまだ未確認のため、次のループで必ず判定する必要があります。

middle が right を追い越した時点で、配列全体が「-1 → 0 → 1」の順に並び替えられています。

コード例

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

const arr = [1, 1, 0, -1, 1, 0, -1, 1, 0, 0, 1];

const sortSpecialArray = (arr = []) => {
  // 2つの要素を入れ替えるヘルパー関数
  const swap = (a, b) => {
    const temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
  };

  let left = 0;
  let middle = 0;
  let right = arr.length - 1;

  while (middle <= right) {
    if (arr[middle] === -1) {
      swap(left++, middle++);
    } else if (arr[middle] === 0) {
      middle++;
    } else if (arr[middle] === 1) {
      swap(right--, middle);
    }
  }
};

sortSpecialArray(arr);
console.log(arr);

出力結果

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

[
  -1, -1, 0, 0, 0,
   0, 1, 1, 1, 1,
   1
]

計算量について

このアルゴリズムの計算量は次のとおりです。

• 時間計算量：O(n) — 各要素は最大1回しか調査されないため、配列を1回の走査だけでソートできます。
• 空間計算量：O(1) — 交換用の一時変数と3つのポインタだけで済み、追加の配列は一切不要です。