20 他のソートざっくり（マージ・クイック・ヒープ）
前章の選択ソートは計算量 O(n²) で、データが多いと実用的ではありません。
この章では「もっと速いソート」の考え方を イメージ重視 でざっくりつかみます。
コードの細かいトレースは練習問題で扱うので、まず「どんな動きか」をイメージしましょう。
1. なぜ速いソートが必要か
| アルゴリズム | 計算量 | n=100,000 の比較回数（目安） |
|---|
| 選択ソート・バブルソート | O(n²) | 約 50 億回 |
| マージ・クイック・ヒープソート | O(n log n) | 約 170 万回 |
約 3,000 倍の差。データが大きくなるほど差は開きます。
2. マージソート
「半分に分割し続け、1要素になったらソートしながら統合して戻る」 ソートです。
分割したデータを統合（マージ）する際、2つのソート済み配列の先頭を比べながら小さい方を取るだけで並び替えができます。
動きのイメージ
マージのポイント：
2つのソート済み配列 {3,8} と {1,5} を統合するとき、先頭を比べて小さい方を取るを繰り返すだけで
{1,3,5,8} が得られます。
| 項目 | マージソート |
|---|
| 平均計算量 | O(n log n) |
| 最悪計算量 | O(n log n)（最悪でも保証） |
| 追加メモリ | O(n)（統合用の作業領域が必要） |
| 安定ソート | はい（同じ値の順序が保たれる） |
3. クイックソート
配列からピボット（基準値）を1つ選び、
「ピボットより小さい組」と「ピボットより大きい組」に分けてから、
それぞれを再帰的にソートします。ピボット自体はその分割の時点で正しい位置に確定します。
動きのイメージ
クイックソートのポイント：
ピボットは分割直後にその最終位置が確定します。あとは左右の組をそれぞれ再帰的にソートすれば全体が完成します。
| 項目 | クイックソート |
|---|
| 平均計算量 | O(n log n)（実用上、最も速いことが多い） |
| 最悪計算量 | O(n²)（ピボット選びが毎回偏ると発生） |
| 追加メモリ | O(log n)（再帰の深さ分） |
| 安定ソート | いいえ |
最悪 O(n²) になる例：
すでに昇順に並んでいる配列に対して毎回先頭をピボットに選ぶと、一方の組が常に空になり、バブルソートと同じ計算量になります。
実用では「ランダムにピボットを選ぶ」などの工夫で回避します。
4. ヒープとヒープソート
ヒープ（heap）は、次の2つの条件を満たす二分木です。
- 完全二分木（上から左詰めで隙間なく埋まっている）
- 親と子の大小ルールがある（最大ヒープ：親 ≧ 子）
最大ヒープでは常に根（一番上）に全体の最大値が入ります。
この性質を使って「最大値を素早く取り出せるデータ構造」として使われます。
最大ヒープのイメージ
兄弟どうしの大小は決まっていないことに注意。上の例で 4（7の子）より 6（7の兄弟）が大きくても構いません。
「親 ≧ 子」だけが条件です。
ヒープソートのアイデア
最大ヒープから「根（最大値）を取り出す」操作を n 回繰り返すことで、降順に値が取り出せます。
取り出すたびにヒープの再構成（末尾を根に移してから適切な位置に押し下げる）が必要ですが、
これが O(log n) で済むため、全体で n × O(log n) = O(n log n) になります。
| 項目 | ヒープソート |
|---|
| 平均計算量 | O(n log n) |
| 最悪計算量 | O(n log n)（最悪でも保証） |
| 追加メモリ | O(1)（追加の配列が不要） |
| 安定ソート | いいえ |
5. ソートアルゴリズム比較
| ソート | 考え方 | 平均 | 最悪 | 安定 |
|---|
| 選択ソート | 最小値を探して先頭へ | O(n²) | O(n²) | いいえ |
| バブルソート | 隣を比べて大きい方を右へ | O(n²) | O(n²) | はい |
| マージソート | 半分に分割してマージ | O(n log n) | O(n log n) | はい |
| クイックソート | ピボットで小大2グループへ | O(n log n) | O(n²) | いいえ |
| ヒープソート | 最大値を繰り返し取り出す | O(n log n) | O(n log n) | いいえ |
使い分けの目安：
・最悪も保証したい + 安定ソートが必要 → マージソート
・速度重視（平均で最速） → クイックソート
・追加メモリを使えない + 最悪も保証したい → ヒープソート
6. 理解度チェック問題
問題20-1
マージソートの動きとして正しいものはどれか。
解説を表示
正解：イ
マージソートは「分割→統合」が特徴です。ア（ピボットで分ける）はクイックソート。ウ（最小値を先頭へ）は選択ソート。
エ（ランダムシャッフル）はボゴソートと呼ばれるアルゴリズムで実用的でなく、明らかに違います。
問題20-2
クイックソートの最悪計算量はどれか。
解説を表示
正解：ウ
クイックソートは平均 O(n log n) ですが、ピボット選びが毎回偏ると最悪 O(n²) になります。
ア（O(log n)）は単純な木の探索相当で、ソート全体では無理。エ（O(2ⁿ)）は指数オーダーで明らかに違います。
問題20-3
最大ヒープの根（一番上の節点）に入っている値はどれか。
解説を表示
正解：ウ
最大ヒープは「親 ≧ 子」が常に成立するので、根は全体の最大値になります。
ア（最小値が根）は最小ヒープの性質です。イ（最後に追加した値）は根に来るとは限りません。
エ（中央値が根）になる理由はありません。
問題20-4
「安定ソートであり、かつ最悪計算量も O(n log n) を保証する」条件を両方満たすのはどれか。
解説を表示
正解：イ
マージソートは最悪でも O(n log n) を保証し、かつ安定ソートです。
ア（クイックソート）は最悪 O(n²) があり安定でもありません。
ウ（ヒープソート）は最悪 O(n log n) ですが安定ではありません。
エ（選択ソート）は O(n²) なので明らかに違います。
発展問題（FE試験スタイル）
ここからは応用問題です。
使う知識はこれまでに学んだ内容（各ソートの特徴・計算量）だけです。
発展問題20-A
配列 {5, 8, 3, 1, 7, 2, 6, 4} にクイックソートを適用する。
先頭の値（5）をピボットとして最初の分割を1回行った後、確実に言えることはどれか。
解説を表示
正解：イ
クイックソートの分割後に確定するのは、ピボット（5）が最終的な正しい位置に収まり、左側に5未満、右側に5超の値が集まることだけです。
左側 {3,1,2,4} や右側 {8,7,6} の内部はまだ並んでいません。
ア・エ（完全にソート済み）は1回の分割ではあり得ません。ウ（左側が昇順）も1回の分割では保証されません。
発展問題20-B
n=1,000,000（100万）のデータを選択ソートとマージソートで並び替えるとき、
比較回数の比（選択ソート÷マージソート）はおよそどのくらいか。
（log₂ 1,000,000 ≒ 20 として計算する）
解説を表示
正解：ウ
選択ソートの比較回数 ≒ n²/2 = (10⁶)²/2 = 5×10¹¹
マージソートの比較回数 ≒ n log₂ n = 10⁶ × 20 = 2×10⁷
比：5×10¹¹ ÷ 2×10⁷ = 約 25,000 倍
ア（マージの方が遅い）は明らかに違います。実際に O(n log n) は O(n²) より圧倒的に速いです。