JavaScript の例で理解するクイックソート

クイックソートは分割統治型のソートアルゴリズムです。ピボット要素を選び、小さい要素が左、大きい要素が右に来るように配列を分割(パーティション)し、その後それぞれの側を再帰的にインプレースでソートします。

多くの人が初めてこれに出会うのは、誰かに見られながらホワイトボードの前に立っているときであり、自信が失われがちなのがパーティションのループです。平均で O(n log n) の時間で動作し、2つ目の配列を確保することなくソートでき、面接官が「これを手でソートしてください」と言うときに真っ先に持ち出すアルゴリズムでもあります。

この記事では3つのことを扱います。直感を養うための読みやすいバージョン、要素が動く様子を実際に見るための手作業によるパーティション処理のトレース、そして面接で実際に書くことになるインプレース実装です。さらに、計算量、ピボットの選び方、安定性についても触れます。

クイックソートアルゴリズムはどのように動作するのか

クイックソートは、選択したピボットを軸に配列を繰り返し分割することでソートを行います。1回のパーティション処理で、ピボットより小さいものはすべてその前に、大きいものはすべてその後ろに来るように要素を再配置します。この時点でピボットは最終的なソート後の位置に確定します。同じ手順を左右のサブ範囲に適用すれば、配列全体がソートされます。

分割統治という形は マージソートと共通していますが、トレードオフは異なります。クイックソートもマージソートも平均は O(n log n) ですが、クイックソートは O(log n) の補助領域でインプレースにソートするのに対し、マージソートは O(n) の追加領域を必要とします。また、マージソートは安定である一方、クイックソートは安定ではありません。クイックソートは、保証された安定性と引き換えに、より少ないメモリオーバーヘッドと実環境での高速さを手にしています。

まずは読みやすいバージョン(filter とスプレッド)

最も読みやすいクイックソートは、filter でパーティションを行い、スプレッド演算子で配列を再構築するものです。再帰を理解するには最速の方法で、教材としては優れていますが、呼び出しのたびに新しい配列を確保するため、本当の意味でのインプレースではなく、追加のメモリを消費します。

function quickSort(arr) {
  if (arr.length <= 1) return arr;

  const [pivot, ...rest] = arr;
  const left = rest.filter((x) => x < pivot);
  const right = rest.filter((x) => x >= pivot);

  return [...quickSort(left), pivot, ...quickSort(right)];
}

quickSort([3, 7, 2, 5, 1, 4, 6, 8]); // [1, 2, 3, 4, 5, 6, 7, 8]

要素数が0または1の配列はすでにソート済みなので、ベースケース(length <= 1)で再帰が停止します。呼び出しごとに3つの新しい配列を作るため、このバージョンのメモリ使用量は一定ではなく入力サイズとともに増加します。考え方を説明するにはこちらを、メモリや面接での期待が重要になる場面では後述のインプレース版を使いましょう。

パーティションはどのように動作するのか

パーティションはクイックソートのエンジンなので、1回のパスをじっくり観察する価値があります。Lomuto 方式では最後の要素をピボットとして取り、走査用インデックス j で範囲を進みながら、次の「ピボットより小さい」要素が入るべき位置を示す境界インデックス i を保持します。arr[j] がピボットより小さいたびに arr[i] と arr[j] を交換し、i を進めます。最後にピボットを位置 i に交換して入れます。

[7, 2, 1, 8, 6, 3, 5, 4] をピボット 4(最後の要素)、i = 0 からトレースしてみましょう。

ピボット 4 はインデックス 3 に収まり、その左に [2,1,3]、右に [6,7,5,8] が並びます。どちらの側もまだソートされていませんが、ピボットの位置は確定しており、2つの側は互いに独立した部分問題になりました。

function partition(arr, lo, hi) {
  const pivot = arr[hi];          // last element as pivot
  let i = lo;                     // boundary for elements < pivot
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]]; // move pivot into place
  return i;
}

面接で書くことになるインプレース版クイックソート

本番向けの形のクイックソートは、上記のパーティション用ヘルパーをそのまま使い、新しい配列を作る代わりにインデックス範囲(lo, hi)に対して再帰します。「クイックソートを実装してください」と言われたときに使うべきはこのバージョンです。1つの配列を破壊的に変更し、追加領域として使うのは再帰スタックだけです。

function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo < hi) {
    const p = partition(arr, lo, hi);
    quickSort(arr, lo, p - 1);
    quickSort(arr, p + 1, hi);
  }
  return arr;
}

quickSort([7, 2, 1, 8, 6, 3, 5, 4]); // [1, 2, 3, 4, 5, 6, 7, 8]

各呼び出しは自身の範囲をパーティションし、その後ピボットの左右2つのサブ範囲に対して再帰します。lo < hi のガードがベースケースです。要素数が0または1の範囲はすでにソート済みだからです。再帰が禁止されている場合(面接でよくある追加質問です)、同じロジックは、コールスタックの代わりに明示的なスタックへ lo/hi のペアをプッシュすることで反復版に変換できます。

計算量、ピボットの選択、そして安定性

クイックソートのコストは、ほぼ完全にピボットによって決まります。分割が均衡していれば、再帰の各レベルでおよそ log n 段階にわたって全要素を1回ずつ処理するため、O(n log n) になります。分割が一貫して偏っていると、再帰の深さは n まで増え、コストは O(n²) に劣化します。インプレースの場合、均衡した入力に対して再帰スタックは O(log n) の領域を占めます。

典型的な罠がこれです。**最初または最後の要素をピボットに選ぶと、すでにソート済みの入力に対してクイックソートは O(n²) の最悪ケースに陥ります。**なぜなら、どのパーティションも要素を1つずつしか剥がせないからです。ソート済み入力による最悪ケースは、中央の要素を選ぶ、median-of-three を使う、あるいはランダムなピボットを選ぶことで回避できます。median-of-three は最初・中央・最後の要素を並べ替えてその中央値を使うもので、ソート済み入力にも逆順ソート済みの敵対的入力にも耐性があります。

function medianOfThree(arr, lo, hi) {
  const mid = Math.floor((lo + hi) / 2);
  if (arr[mid] < arr[lo]) [arr[lo], arr[mid]] = [arr[mid], arr[lo]];
  if (arr[hi]  < arr[lo]) [arr[lo], arr[hi]]  = [arr[hi], arr[lo]];
  if (arr[hi]  < arr[mid]) [arr[mid], arr[hi]] = [arr[hi], arr[mid]];
  // median now sits at mid; move it to hi so Lomuto uses it as the pivot
  [arr[mid], arr[hi]] = [arr[hi], arr[mid]];
  return arr[hi];
}

どんなピボット戦略をとっても取り戻せない性質が1つあります。クイックソートは安定ソートではないため、等しい要素が元の位置関係から並び替えられる可能性があるという点です。これは、レコードを副次キーでソートしつつ主たる並び順が保たれることを期待している場合に問題になります。

JavaScript の組み込みソートはクイックソートなのか

いいえ。クイックソートというアルゴリズムは不安定ですが、JavaScript 組み込みの Array.prototype.sort は ES2019、すなわち言語標準の第10版以降、安定であることが保証されています。V8 は v7.0 および Chrome 70 以降、Timsort で配列をソートしています。これは、すでに整列済みのデータの連なり(run)を活用し、等しい要素を見つけた順序のまま保持するマージソートです。他の主要エンジンもすべて、仕様によって同じ安定性要件を課されています。したがって「クイックソートは不安定」というのはアルゴリズムについての説明であり、現代のブラウザにおける組み込み sort についての説明ではありません。

クイックソートがその評価を得ているのは、引き締まったパーティションループ、インプレース動作、そして平均 O(n log n) の速度によるものです。ただし、ピボットを配列の端から遠ざけておく限りにおいて、です。上記のインプレース版を median-of-three またはランダムピボットとともに実装し、ソート済み入力に対して実行して破綻しないことを確認しましょう。そうすれば、求められたときにクイックソートを書くことも、そのトレードオフを説明することもできるようになります。

よくある質問

マージソートではなくクイックソートを使うべきなのはどんなときですか?

メモリに制約があり、インプレースでソートしたい場合にクイックソートを使いましょう。マージソートが O(n) の追加配列を必要とするのに対し、クイックソートは再帰スタックのための O(log n) の補助領域しか必要としません。どちらも平均は O(n log n) ですが、典型的なデータでは実際にはクイックソートの方が高速です。安定性の保証や O(n log n) の最悪ケース保証が必要な場合はマージソートを選びましょう。クイックソートは O(n の 2 乗) に劣化する可能性があるためです。

なぜクイックソートはすでにソート済みの配列で O(n の 2 乗) になるのですか?

最初または最後の要素に固定したピボットは、ソート済み入力に対して O(n の 2 乗) に劣化します。どのパーティションでもピボットが端に置かれ、片方が空のサブ範囲、もう片方が n マイナス 1 個の要素の範囲になるからです。その結果、再帰は log n 段ではなく n 段になり、各段で線形の処理が行われます。対策は、中央の要素を選ぶ、median-of-three を使う、ランダムなピボットを選ぶことで、いずれもソート済みデータに対して均衡した分割を回復します。

JavaScript の Array.prototype.sort はクイックソートで実装されていますか?

いいえ。現代のエンジンは組み込みソートにクイックソートを使っていません。V8 は v7.0 および Chrome 70 以降 Timsort を使用しています。これは、すでに整列済みのデータの連なりを活用し、等しい要素の順序を保持するマージソートです。ES2019 以降、ECMAScript 仕様は Array.prototype.sort が安定であることを要求しており、主要なエンジンはすべて安定ソートを提供しています。したがって、クイックソートというアルゴリズムは不安定ですが、組み込みソートはクイックソートではなく、安定であることが保証されています。

Lomuto 方式と Hoare 方式のパーティションの違いは何ですか?

Lomuto は単一の走査インデックスを使い、通常は最後の要素をピボットとして取り、より小さい要素を境界インデックスの方へ交換していきます。書くのもトレースするのも簡単です。Hoare は両端から内側に向かって動く 2 つのポインタを使い、一般に交換回数が少なく、実際には高速です。どちらもインプレースでパーティションし分割点を返しますが、Hoare が返すインデックスは、Lomuto のようにピボットを最終位置に配置するわけではありません。

再帰版のクイックソートを反復版に変換するにはどうすればよいですか?

コールスタックを、インデックス範囲を保持する明示的なスタックに置き換えます。最初の lo と hi のペアをプッシュし、スタックが空でない間ループします。範囲をポップし、パーティションしてピボットインデックス p を得て、lo から p マイナス 1、および p プラス 1 から hi の 2 つのサブ範囲を、要素が 2 つ以上含まれる場合にスタックへ戻します。これにより再帰を避けつつ同じ結果が得られます。面接でよくある追加質問です。