これまで3回にわたって、「バブルソート問題をC言語のコードで確認してみよう！」、「選択ソート問題をC言語のコードで確認してみよう！」、「挿入ソート問題をC言語のコードで確認してみよう！」と、基本的なO(n²)ソート3種をそれぞれトレース問題形式で確認してきた。
今回はこの3つを並べて、「何が同じで、何が違うのか」を整理する回にする。個別に見ているときは気づきにくかった違いが、並べることで見えてくるはずである。
同じ配列を3つのアルゴリズムにかけてみる
{5, 2, 8, 1, 9, 3} という同じ配列を、3つのソートにそれぞれかけた結果を並べてみる。
バブルソート
ソート前: 5 2 8 1 9 3
1回目のパス後: 2 5 1 8 3 9
2回目のパス後: 2 1 5 3 8 9
3回目のパス後: 1 2 3 5 8 9
4回目のパス後: 1 2 3 5 8 9
ソート後: 1 2 3 5 8 9
バブルソートだけ4回目のパスで処理が止まっている点に気づかれただろうか。4回目のパスで交換が1回も起きなかったため、swappedフラグによる早期終了が働き、5回目のパスに入らずに打ち切られている。これは、早期終了の仕組みを持つのはバブルソートだけという違いをそのまま表している。
選択ソート
ソート前: 5 2 8 1 9 3
1回目のパス後: 1 2 8 5 9 3
2回目のパス後: 1 2 8 5 9 3
3回目のパス後: 1 2 3 5 9 8
4回目のパス後: 1 2 3 5 9 8
5回目のパス後: 1 2 3 5 8 9
ソート後: 1 2 3 5 8 9
挿入ソート
ソート前: 5 2 8 1 9 3
1回目のパス後: 2 5 8 1 9 3
2回目のパス後: 2 5 8 1 9 3
3回目のパス後: 1 2 5 8 9 3
4回目のパス後: 1 2 5 8 9 3
5回目のパス後: 1 2 3 5 8 9
ソート後: 1 2 3 5 8 9
最終結果はどれも同じ 1 2 3 5 8 9 になるが、そこに至るまでの配列の変化のしかたが全く違うことが一目でわかる。この「過程の違い」こそが、3つのアルゴリズムを見分ける最大の手がかりである。
ロジックの本質的な違い
- バブルソート：隣り合う2要素を比較し、大小が逆なら交換する、を配列の端まで繰り返す。1回のパスで複数回の交換が起きうる
- 選択ソート：未整列部分から最小値を探し出し、先頭の要素と交換する。1回のパスで交換は最大1回だけ
- 挿入ソート：整列済み部分に対して、次の要素を正しい位置まで比較しながら挿入する。交換ではなく「シフト」で位置を空ける
3つとも「未整列部分」と「整列済み部分」という2つの領域を意識しながら動く点は共通している。ただし、その領域の広がり方が異なる。バブルソートと選択ソートは末尾側から整列済みが確定していくのに対し、挿入ソートは先頭側から整列済みが広がっていくという向きの違いがある。
比較表
| バブルソート | 選択ソート | 挿入ソート | |
|---|---|---|---|
| 基本動作 | 隣接比較＋交換 | 最小値探索＋交換 | 比較しながらシフト＋挿入 |
| 最悪計算量 | O(n²) | O(n²) | O(n²) |
| 最良計算量 | O(n)（改良版・早期終了あり） | O(n²)（並び方に関係なく一定） | O(n)（ほぼ整列済みの場合） |
| 交換／シフト回数 | 多い（比較のたびに発生しうる） | 少ない（1パス最大1回の交換） | 状態による（シフトの回数がデータ依存） |
| 安定性 | 安定 | 不安定 | 安定 |
| 早期終了の仕組み | あり（交換が起きなければ終了） | なし | なし（ただしシフトが起きなければ実質的に早い） |
この表の中で、FE試験のトレース問題・穴埋め問題として特に狙われやすいのは安定性と最良計算量の2点である。「不安定なソートはどれか」「データがほぼ整列済みのときに最も効率がよいのはどれか」といった問いには、この比較表を頭に入れておけば即答できる。
試験問題を解くときの読み方のコツ
- まず外側ループと内側ループがそれぞれ何を表しているかを特定する（確定させる位置なのか、探索範囲なのか、挿入位置探しなのか）
- 交換処理・シフト処理が内側ループの中にあるか外にあるかを見る。バブルソートは内側ループの中、選択ソートは内側ループの外（パスの最後）、挿入ソートは内側ループ自体がシフト処理という構造になっている
- 早期終了の判定（フラグ変数の有無）があるかどうかを確認する。あればバブルソートの改良版である可能性が高い
- 迷ったときは、この記事の比較表の「基本動作」列に立ち返るとアルゴリズムを取り違えにくい
まとめ
- 3つのソートは最終結果こそ同じでも、配列が変化していく過程は大きく異なる
- バブルソート・選択ソートは末尾側から、挿入ソートは先頭側から整列済み領域が広がっていく
- FE試験では「安定性」と「最良計算量」の比較が特に狙われやすい
これでバブル・選択・挿入という基本的なO(n²)ソート3種の学習が一区切りとなった。次回以降は、選択・挿入ソートをGo・Kotlinに移植してC言語と比較し、そしてより発展的なソートアルゴリズム（マージソート・クイックソートなど）を取り上げていく予定である。
この記事で扱ったコードは、GitHubの c-language-studies リポジトリ （FE-algorithm/01_bubble_sort/、FE-algorithm/03_selection_sort/、FE-algorithm/04_insertion_sort/）で公開している。
コメント