クイックソートの仕組みを徹底解説！アニメーションで学ぶ「圧倒的平均最速」ソート【ソートアルゴリズム入門】#9

図解で分かる、インタラクティブツール付き、クイックソートとは？分割統治法の代表例 — クイックソートの説明をする記事のサムネイル。記事内では、クイックソートとは？という疑問からソートの仕組みまで詳しく紹介

分割統治法を使ったソートの王道”クイックソート”

以前の記事で、分割統治法を用いたアルゴリズムとして、常に安定した \(O(n \log n \) の性能を誇る「マージソート」を紹介しました。

一つ前の記事 “分割統治法を純粋に遂行”マージソート

マージソートの仕組みを徹底解説！アニメーションで学ぶ「分割統治」ソート・併合ソート【ソートアルゴリズム入門】#6

「マージソート」は「分割統治法」に基づく高速なソートです。O(N^2)の単純ソートとは異なり、O(N log N)の計算量を実現します。データを半分に「分割」し、ソートしながら賢く「結合（マージ）」する仕組みを図解します。

“分割統治法”について理解する

分割統治法の3ステップ（分割・統治・結合）を図解したサムネイル画像。「「分割統治法」がわかれば、もう初心者じゃない！」というキャッチコピー入り。

分割統治法とは？高速なソートアルゴリズム【ソートアルゴリズム入門】#5

「分割統治法」とは？難しい問題を「小さく分けて、後で合体する」ことで高速に解くアルゴリズム戦略です。O(N^2)の壁を破るO(N log N)の鍵となる、マージソートやクイックソートの基本思想を図解します。

マージソートは「分割は単純、結合は賢く」という戦略でしたね。

今回は、同じ「分割統治法」を使いながら、逆のアプローチをとるアルゴリズム、「クイックソート（Quick Sort）」を解説します。

クイックソートは、その名の通り非常に高速で、多くのプログラミング言語で標準ソートとして採用されている「ソートの王様」とも呼ばれるアルゴリズムです。

クイックソートの実行例アニメーション

分割統治法の代表例クイックソートの実行例。クイックソートを手元で試せるツールの実行結果。

クイックソートの実行例　アニメーション

1. クイックソート（Quick Sort）とは？

クイックソートも「分割統治法」に基づいています。しかし、マージソートとは対照的に、「分割の段階で賢く並べ替え、結合を不要にする」アルゴリズムです。

マージソート:
1. 分割: とにかく半分に分ける。（作業は単純）
2. 結合: ソート済みの2つを賢くマージする。（作業が重い）
クイックソート:
1. 分割: ある「基準値」を決め、それより小さい/大きいで分ける。（作業が重い）
2. 結合: 分割が終わればソートも終わっているので、作業は不要。

この「分割」のステップがクイックソートの核であり、「パーティション（Partition）」操作と呼ばれます。

2. クイックソートの分割統治方法

例として、マージソートと同様のトランプの配列 [9, 6, Q, 3, 2, 1, J, 8, 7, 5, 10. 4] を並び替える例でアルゴリズムを紹介します。

(1) 分割 (Divide) と統治 (Conquer)

クイックソートでは「分割」と「統治（再帰呼び出し）」が密接に関連しています。

ステップ1: グループ全体 [9, 6, Q, 1, 2, 3, J, 10, 8, 7, 5, 4]

ピボット（基準値）の選択:まず、グループ内から「ピボット」となる基準値を1つ選びます。選び方はいろいろありますが、ここでは単純に一番右の「4」をピボットに選びます。[9, 6, Q, 1, 2, 3, J, 10, 8, 7, 5, 4 ] (ピボット)
パーティション（分割）操作:ピボット以外の要素（左端から）を順に見ていき、「ピボット”4″以下のグループ」と「ピボット”4″より大きいグループ」に振り分けます。（※実際の実装はもう少し複雑ですが、ここでは概念的な動きを示します）
- 9 \(\to\) 大きいグループへ
- 6 \(\to\) 大きいグループへ
- Q \(\to\) 大きいグループへ
- 1 \(\to\) 小さいグループへ
- 2 \(\to\) 小さいグループへ
- 3 \(\to\) 小さいグループへ
- …

これを最後まで行うと、配列が以下のように並び替えられます。

[1, 2, 3] (小さいグループ) \(\to\) 4 \(\to\) [9, 6, Q, J, 10, 8, 7, 5] (大きいグループ)

ピボットだった「4」を2つのグループの間に置きます。この時点で、「4」は最終的な正しい位置に確定しました。

ステップ2: 2つのグループを、それぞれ「統治」する

次に、分割してできた2つのグループ（小さいグループと大きいグループ）に対して、まったく同じこと（クイックソート）を再帰的に行います。

左グループ [1, 2, 3] の処理:
1. ピボットに「3」を選ぶ。
2. パーティション操作 \(\to\) [1, 2] (小さい) \(\to\) 3 \(\to\) [] (大きい: なし)
右グループ [9, 6, Q, J, 10, 8, 7, 5] の処理:
1. ピボットに「5」を選ぶ。
2. パーティション操作 \(\to\) [] (小さい: なし) \(\to\) 5 \(\to\) [9, 6, Q, J, 10, 8, 7]

ステップ3: さらに再帰…

これを、分割したグループの要素が1つ（または0個）になるまで繰り返します。

(2) 結合 (Combine)

マージソートの「結合」は、2つのソート済みリストを比較しながらマージする重い処理でした。

クイックソートの「結合」はどうでしょう？

ステップ1の時点で、[小さいグループ] \(\to\) ピボット \(\to\) [大きいグループ] という並びが確定しています。

それぞれのグループを再帰的にソートし終えたら、それらをただ並べるだけです。特別な結合操作は一切不要です。これがクイックソートが高速な理由の一つです。

3. クイックソートの動きを見てみよう！

クイックソートで並び替えを試せます。ステップ実行ボタンを押して、並び替えを進めてみてください。

色が濃い部分が今処理をしているグループ（パーティション対象）で、ピボットに使用している要素を赤色にしています。

「再配置」を押して開始してください

4. クイックソートの疑似コード (ソートの手順)

クイックソートは、再帰関数1つで表現できます。（パーティション操作を関数内に含める方法）

// L: ソートしたいリスト
// low, high: ソート対象の「範囲」を示すインデックス
algorithm QuickSort(L, low, high) is
  
  // (1) 再帰の停止条件: 範囲がない、または1つだけなら終了
  if low >= high then
    return
  end
  
  // (2) 分割 (Partition)
  // pivot_index ← Partition(L, low, high)
  // （Partition操作の結果、ピボットが最終的な位置 (pivot_index) に移動する）
  
  // --- Partition操作の簡易な例 (ピボットを L[high] とする) ---
  pivot ← L[high]
  i ← low // 「小さいグループ」の右端
  
  // j: 未処理グループの先頭 (low から high-1 まで)
  for j from low to high-1 do
    if L[j] <= pivot then
      swap(L[i], L[j]) // L[j]を「小さいグループ」の末尾に追加
      i ← i + 1
    end
  end
  
  // 最後にピボットを「小さい」と「大きい」の間に移動
  swap(L[i], L[high])
  pivot_index ← i
  // --- Partition操作ここまで ---
  

  // (3) 統治 (Conquer)
  // ピボットの「左側」を再帰的にソート
  QuickSort(L, low, pivot_index - 1)
  
  // ピボットの「右側」を再帰的にソート
  QuickSort(L, high, pivot_index + 1)

end