こんにちは！今日は 基本情報技術者試験 の「ソート（整列）」分野を勉強しましたので解説します。
ソートは データを小さい順・大きい順に並び替える処理 のこと。
試験では「整列方法の特徴」「比較回数・計算量」「アルゴリズムの仕組み」がよく問われます。
この記事で分かること（目次）
1. 基本交換法（バブルソート）
仕組み
お隣同士のデータを比べて、順序が逆なら入れ替える。これを繰り返す方法です。
まるで あぶく（泡）が水面にのぼるように大きい値が後ろに移動する ので「バブルソート」とも呼ばれます。
比較回数
- 最大で n(n−1)/2 回（nはデータ数）。
- 例：5個なら最大 10 回比較。
- 効率は悪い → 大きなデータには不向き。
2. 基本挿入法（挿入ソート）
仕組み
新しいカードを手札に入れるときに、順番を守って差し込むやり方です。
小さい範囲の並び替えを少しずつ広げていくイメージ。
比較回数
- 最悪：n(n−1)/2 回
- すでに整列済みなら：n−1 回（とても効率的！）
3. 基本選択法（選択ソート）
仕組み
「残りの中で一番小さいものを探して、前から順番に置く」方法。
運動会で「背の順に並ぶときに、毎回一番小さい人を呼ぶ」イメージです。
比較回数
- 常に n(n−1)/2 回（整列具合に左右されない）。
4. シェルソート
仕組み
挿入ソートを改良したもの。
データを「一定の間隔ごと」にグループに分け、まずグループ内で並べ替え、その後間隔を狭めていく。
→ 最後は普通の挿入ソートをやるけど、データがある程度整っているから速い。
比較回数
- 厳密には間隔の取り方で変動。
- 平均 O(n log n) くらいで、挿入ソートよりだいぶ速い。
5. ヒープソート
仕組み
データを ヒープ木（親が子より常に大きい/小さいという条件を持つ二分木）に変換して、根から順に取り出す方法。
「おもちゃ箱の中から毎回一番大きいブロックを簡単に取り出せる仕組み」を作るイメージ。
比較回数
- O(n log n)（効率が良い）。
- クイックソートと並ぶ高速なソート法。
6. クイックソート
仕組み
基準（ピボット）を決め、
「小さいグループ」「大きいグループ」に分けて、再帰的に整列。
とても効率が良く、実際のプログラムでもよく使われます。
比較回数
- 平均：O(n log n)（高速）
- 最悪：O(n²)（偏りがあると遅い）
ソート比較（まとめ表）
| 方法 | 最悪比較回数 | 平均的な計算量 | 特徴 |
|---|---|---|---|
| 基本交換法 | n² | n² | 実装簡単・遅い |
| 基本挿入法 | n² | n² | データがほぼ整列済みなら速い |
| 基本選択法 | n² | n² | 安定して遅い |
| シェルソート | 不定 | n log n | 挿入ソートの改良版 |
| ヒープソート | n log n | n log n | 安定した高速 |
| クイックソート | n² | n log n | 平均的に最速 |
7. 過去問例（基本情報技術者試験）
問1
次のソートのうち、データがあらかじめ整列済みのときに、最小の比較回数で済むのはどれか。
- バブルソート
- 挿入ソート
- 選択ソート
- ヒープソート
👉 正解：2（挿入ソート）
問2
クイックソートの計算量として、平均的な場合に最も近いものはどれか。
- O(n)
- O(n log n)
- O(n²)
- O(log n)
👉 正解：2（O(n log n)）
まとめ
- バブル・挿入・選択は基本だけど遅い。
- クイックソート・ヒープソートは高速。
- 「比較回数」や「効率の違い」を理解することが試験対策のポイント！