クイックソート・その他
まず結論
ソートアルゴリズムは4種類を比較で覚える。クイックソートは平均O(n log n)で最速クラスだが最悪O(n²)、マージソートは常にO(n log n)で安定。試験ではどのアルゴリズムがどの計算量かを問われる。
⚡ クイックソート
クイックソートは「分割統治法」を使う高速なソートアルゴリズムです。
1
ピボットを選ぶ
配列から基準値（ピボット）を1つ選ぶ。よく使われるのは先頭・末尾・中央の値。
2
分割（partition）
ピボットより小さい値を左グループ、大きい値を右グループに分ける。
3
再帰的に繰り返す
左グループ・右グループに対してそれぞれ同じ操作を繰り返す（再帰）。
ピボット 3 を使って [5, 3, 1, 4, 2] を分割する例：
初期配列
5
3
1
4
2
紫 = ピボット(3) 青 = 比較対象
ピボット3と比較して分割
左グループ（3より小さい）
1
2
+
ピボット
3
+
右グループ（3より大きい）
5
4
各グループに再帰適用 → 最終結果
1
2
3
4
5
計算量：平均 O(n log n) ／ 最悪 O(n²)（ピボットが常に最大値・最小値になる場合）
安定性：不安定ソート（同じ値の順序が変わりうる）
安定性：不安定ソート（同じ値の順序が変わりうる）
📊 その他のソートアルゴリズム
選択ソート（Selection Sort）
未整列部分から最小値を探して先頭と交換する。シンプルだが常に O(n²)。
1
5
3
4
2
最小値1を見つけて先頭(5)と交換 → 赤 = 発見した最小値、黄 = 交換元
挿入ソート（Insertion Sort）
左側の整列済み部分に、未整列の要素を適切な位置に挿入していく。すでにほぼ整列済みのデータではO(n)に近い。
1
3
5
4
2
緑 = 整列済み、青 = これから挿入する値(4)
マージソート（Merge Sort）
配列を半分に分割し続け、最後にマージ（合併）しながら整列する。常にO(n log n)で安定ソート。大量データに向く。
[5, 3, 1, 4, 2]
↓ 分割
[5, 3][1, 4, 2]
↓ さらに分割 → 整列
[3, 5][1, 2, 4]
↓ マージ
[1, 2, 3, 4, 5]
📋 ソートアルゴリズム比較表
| アルゴリズム | 平均計算量 | 最悪計算量 | 安定性 | 特徴 |
|---|---|---|---|---|
| バブルソート | O(n²) | O(n²) | ✅ 安定 | 隣同士を比較・交換 |
| クイックソート | O(n log n) | O(n²) | ❌ 不安定 | ピボットで分割再帰 |
| 選択ソート | O(n²) | O(n²) | ❌ 不安定 | 最小値を選んで交換 |
| 挿入ソート | O(n²) | O(n²) | ✅ 安定 | 既ソートデータでO(n) |
| マージソート | O(n log n) | O(n log n) | ✅ 安定 | 分割→マージ。常に安定 |
安定ソートとは？ 同じ値を持つ要素の元の順序が保たれるソート。バブル・挿入・マージが安定。クイック・選択は不安定。
🎯 試験での出方
- 「クイックソートの平均計算量は？」→ O(n log n)
- 「安定ソートはどれか？」→ バブル・挿入・マージ（クイック・選択は不安定）
- 「すでにほぼ整列済みのデータで最も効率が良いのは？」→ 挿入ソート（O(n)に近づく）
- 「最悪計算量が常にO(n log n)なのは？」→ マージソート
- ピボットの選び方によってクイックソートの性能が大きく変わる点も出題される
⚠️ よくある間違い
- クイックソートが「常にO(n log n)」と思い込む → 最悪はO(n²)
- 選択ソートを「安定ソート」と思い込む → 不安定
- マージソートはメモリを追加で使う（作業領域がO(n)必要）点を忘れる
- 「高速なソートアルゴリズム」≠ クイックソートだけ。マージソートも同等
✍️ 確認クイズ
Q1. クイックソートの平均的な計算量として正しいものはどれか？
正解：ウ O(n log n)
クイックソートはピボットで配列をおよそ半分に分割し再帰的に処理するため、平均でO(n log n)になります。ただし最悪（ピボットが常に最大・最小値）の場合はO(n²)になる点も覚えておきましょう。
クイックソートはピボットで配列をおよそ半分に分割し再帰的に処理するため、平均でO(n log n)になります。ただし最悪（ピボットが常に最大・最小値）の場合はO(n²)になる点も覚えておきましょう。
Q2. 次のうち「安定ソート」に該当するものを全て含む選択肢はどれか？
正解：イ バブルソート、挿入ソート、マージソート
安定ソートとは同じ値の要素の元の順序が保たれるソートです。バブル・挿入・マージが安定。クイックソートと選択ソートは不安定ソートです。
安定ソートとは同じ値の要素の元の順序が保たれるソートです。バブル・挿入・マージが安定。クイックソートと選択ソートは不安定ソートです。
Q3. 「データがほぼ整列済みの場合」に最も効率が良いソートアルゴリズムはどれか？
正解：ウ 挿入ソート
挿入ソートはデータがほぼ整列済みの場合、ほとんど交換が発生しないためO(n)に近い性能を発揮します。クイックソートは逆に既ソートデータで最悪計算量O(n²)になることがあります。
挿入ソートはデータがほぼ整列済みの場合、ほとんど交換が発生しないためO(n)に近い性能を発揮します。クイックソートは逆に既ソートデータで最悪計算量O(n²)になることがあります。
Q4. クイックソートのピボット選択がアルゴリズムの性能に与える影響として正しいものはどれか？
正解：ウ
クイックソートはピボットによって配列を均等に分割できれば平均O(n log n)です。しかしピボットが常に最小値または最大値（例：既ソートデータに先頭をピボットとして選択）だと、分割が1:n-1と偏り再帰がn段になるため最悪O(n²)になります。ランダムピボットはこの最悪ケースを避けるために有効な手法です。
クイックソートはピボットによって配列を均等に分割できれば平均O(n log n)です。しかしピボットが常に最小値または最大値（例：既ソートデータに先頭をピボットとして選択）だと、分割が1:n-1と偏り再帰がn段になるため最悪O(n²)になります。ランダムピボットはこの最悪ケースを避けるために有効な手法です。
Q5. 全てのソートアルゴリズムについて計算量を正しく述べているものはどれか？
正解：ウ
ソートアルゴリズムの計算量まとめ：バブルソート=O(n²)、選択ソート=O(n²)、挿入ソート=O(n²)（最良O(n)）、マージソート=常にO(n log n)、クイックソート=平均O(n log n)・最悪O(n²)。試験では「常にO(n log n)」のマージソートと「平均O(n log n)」のクイックソートの違いが問われることがあります。
ソートアルゴリズムの計算量まとめ：バブルソート=O(n²)、選択ソート=O(n²)、挿入ソート=O(n²)（最良O(n)）、マージソート=常にO(n log n)、クイックソート=平均O(n log n)・最悪O(n²)。試験では「常にO(n log n)」のマージソートと「平均O(n log n)」のクイックソートの違いが問われることがあります。
Sponsor Link