ソートアルゴリズム
バラバラのデータを大きさ順に並び替える処理をソート（Sort：整列）と呼びます。ソートは二分探索の大前提であり、コンピュータサイエンスで最も研究し尽くされた基本アルゴリズムです。単純だが遅い方法と、実用的で超高速な方法を対比しながら、その仕組みを理解しましょう。
1. なぜソートが必要なのか？
データを並び替える目的は、単に人間が見やすくするためだけではありません。
前述の通り、1億件のデータから線形探索 O(N) を行うと最大1億回かかりますが、事前にソートされてさえいれば、二分探索 O(log N) を使ってわずか27回の比較で見つけ出せます。
データを高速に探索・分析・加工するには、事前のソートがほぼ必須の前提条件です。ソートの高速化はコンピュータ全体の高速化に直結します。
2. バブルソート（Bubble Sort）：直感的だが遅いアルゴリズム
もっとも単純で直感的なソートの1つがバブルソート（泡ソート）です。
配列の端からスタートし、「隣り合う2つを比較して順序が逆なら交換する」という処理を繰り返します。泡が下から上へ浮かぶように見えることから、この名が付きました。
このアルゴリズムは、すべての要素が整列し終わるまで、二重のループで比較を繰り返すため、計算量はデータ数Nに対して O(N²) になります。 Nが10倍になると計算の手間は100倍になり、Nが100万件になると計算回数は1兆回（＝遅すぎて実用に耐えない）に達してしまいます。
3. クイックソート（Quick Sort）：圧倒的に速い「分割統治」
実用上最も広く使われているソートがクイックソート（Quick Sort）です。
クイックソートは分割統治法（Divide and Conquer）を採用しています。大きな問題を小さな問題に分割して解くアプローチです。
- データ群の中から、基準となる値を1つ適当に選びます。この値をピボット（Pivot）と呼びます。
- ピボットよりも「小さい値のグループ」と、「大きい値のグループ」の2つにデータを左右に振り分けます。
- 分割された左右それぞれのグループに対して、再び独立してステップ1（ピボットの選定と分割）を再帰的に適用します。
- これ以上分割できなくなるまで（要素数が1個になるまで）繰り返すと、全体のソートが美しく完了します。
毎回ほぼ半分ずつに切り分けていく再帰プロセスにより、計算量は平均 O(N log N) にまで下がります。
Nが100万件の場合を比較すると、バブルソート O(N²) が 1兆回 の計算を要するのに対して、クイックソート O(N log N) は約 2000万回（$1000000 \times 20$）の計算ステップで完了します。実行速度にして数万倍、数時間かかる処理が「一瞬（コンマ数秒）」で終わる決定的な差になります。
4. 代表的なソートの比較表
ソートアルゴリズムには、他にもメモリ消費量や「安定性（同じ値のデータの順序が崩れないか）」などの特徴があり、用途に合わせて選ばれます。
| アルゴリズム | 平均計算量 | 最悪計算量 | メモリ効率 | 安定性 | 特徴 |
|---|---|---|---|---|---|
| バブルソート | O(N²) | O(N²) | 極めて高い | 安定 | 極めてシンプルだが、遅いため実用には使われない。 |
| クイックソート | O(N log N) | O(N²) | 高い | 不安定 | 実用上もっとも高速。ただし、ピボットの選び方によっては最悪のケースがある。 |
| マージソート | O(N log N) | O(N log N) | やや低い | 安定 | 常に安定した速度。ただし、データを並び替えるための余分なワーク領域メモリが必要。 |
第5章では、アルゴリズムとデータ構造を学びました。メモリの物理配置からデータの抽象化、高速な探索・加工まで、プログラムの論理的な骨組みを理解できたはずです。
次の第6章では、単体のコンピュータを飛び出し、無数のマシンが世界規模で繋がる「ネットワーク」の仕組みを探求していきましょう。