ソートアルゴリズムとは（全体像）
ソートは、バラバラのデータを大小の順に並べ替えること。Excelの並べ替え、点数順の席替えなど、身近な場面で使われている。
並べ替えのやり方は何種類もあり、速さ（計算量）が違う。だから、データの量や性質に合わせて選ぶ。まずは大きく2つのグループで押さえる。
- O(n²)グループ … 単純で分かりやすいが、データが増えると遅い。小規模向き。
- O(n log n)グループ … 仕組みは複雑だが、大きなデータでも速い。実用的。
ここで「O(n²)」「O(n log n)」は速さの目安で、nはデータの個数。O(n²)はデータが10倍になると約100倍遅くなるが、O(n log n)はそこまで遅くならない——この差が実用での大きな違いだ。
詳しく：2グループとクイックソートだけ覚えれば戦える
ここが記事の心臓部。代表的なソートをグループで整理する。
ソートの2グループ
| グループ | 代表 | 特徴 |
|---|---|---|
| O(n²)（遅い） | バブル・選択・挿入 | 単純・小規模向き |
| O(n log 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 log n)を保証し、安定（同じ値の元の順番を保つ）という長所がある（そのかわり追加のメモリが要る）。
なお、安定性とは「同じ値の要素の順番が、並べ替え後も保たれるか」のこと。安定が必要なら、マージソートや挿入ソートを選ぶ。つまり、速さだけでなく安定性やメモリも見て選ぶ、というわけだね。
わかりやすく言い換えると
要するに、ソートは「並べ替えのやり方くらべ」だ。
①O(n²)グループ … 手作業っぽい素朴なやり方。少ない枚数なら問題ないが、枚数が増えるとぐっと時間がかかる。
②O(n log n)グループ … 賢い手順で、大量でも手早く片づく。
クイックソートは「ふだんは最速の達人」だけど、運が悪いとO(n²)まで遅くなることがある。確実さがほしいなら、最悪でも速さを保証するマージソート——というふうに、場面で選ぶ、というわけだね。
試験のツボ
🔴 一番出る：クイックソートの平均と最悪
①平均はO(n log n)で実用的に最速クラス
②最悪はO(n²)になることがある（いつも速いわけではない）
🔴 次に出る：2グループの区別
①O(n²)＝バブル・選択・挿入（単純・小規模向き）
②O(n log n)＝マージ・ヒープ・クイック（実用・大規模向き）
🟡 押さえると安定：安定性とマージソート
①安定性＝同じ値の順番が保たれるか
②マージソートは最悪でもO(n log n)保証・安定（追加メモリは要る）
よくある間違い
①「クイックソートはどんなときも必ずO(n log n)である」→ ✗ 平均はO(n log n)だが、最悪はO(n²)になることがある。
②「ソートはどれを使っても速さも性質も同じである」→ ✗ 計算量・安定性・メモリが違うので、場面で使い分ける。
③「マージソートは最悪の場合だけO(n²)に落ちる」→ ✗ マージソートは最悪でもO(n log n)を保証する。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（クイックソート）
クイックソートの計算量に関する次の記述のうち、正しいものはどれか。
- 平均はO(n log n)で実用的に速いが、最悪はO(n²)になることがある
- どんな場合も必ずO(n log n)で、最悪でも遅くなることはない手法である
- 平均でもO(n²)と遅く、データが少ないときにしか使えない手法である
- 計算量はデータの個数と無関係で、つねに一定時間で終わる手法である
解答は 1 だよ。
クイックソートは平均O(n log n)で実用的に速いけれど、最悪の場合はO(n²)になることがあるんだ。「いつも最速」と思い込まないのがポイントだよ。
選択肢2は「最悪でも遅くならない」が誤り。選択肢3は「平均もO(n²)」が誤り。選択肢4は「個数と無関係」が誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | 平均O(n log n)・最悪O(n²) |
| 2 | ✗ | 最悪はO(n²)になる |
| 3 | ✗ | 平均はO(n log n)で速い |
| 4 | ✗ | 個数で計算量は変わる |
オリジナル問題2（2グループ）
ソートアルゴリズムの計算量に関する次の記述のうち、正しいものはどれか。
- バブルソートはO(n log n)で、マージソートはO(n²)に分類されるものである
- すべてのソートはO(n²)で、計算量による速さの違いはないとされている
- バブル・選択・挿入はO(n²)、マージ・ヒープ・クイックはO(n log n)だ
- すべてのソートはO(1)で、データの個数によらず一瞬で終わるものである
解答は 3 だよ。
バブル・選択・挿入はO(n²)（遅い基本）、マージ・ヒープ・クイックはO(n log n)（速い実用）が目安なんだ。データが多いときは後者を選ぶよ。
選択肢1はバブルとマージの計算量が逆。選択肢2は「違いがない」が誤り。選択肢4は「O(1)」が誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | バブルとマージの計算量が逆 |
| 2 | ✗ | 計算量に違いがある |
| 3 | ✓ | O(n²)グループとO(n log n)グループ |
| 4 | ✗ | O(1)では並べ替えられない |
オリジナル問題3（安定性とマージソート）
ソートの安定性とマージソートに関する次の記述のうち、正しいものはどれか。
- マージソートは最悪の場合だけO(n²)に落ちる、不安定なソートである
- マージソートは最悪でもO(n log n)を保証し、安定なソートだ
- 安定性とは計算量のことで、同じ値の順番が保たれるかとは無関係である
- マージソートは追加のメモリをいっさい使わずに並べ替える手法である
解答は 2 だよ。
マージソートは最悪でもO(n log n)を保証し、安定（同じ値の順番が保たれる）なんだ。確実さや安定性がほしいときに頼りになるよ（そのかわり追加メモリは要る）。
選択肢1は「最悪O(n²)・不安定」が誤り。選択肢3は「安定性＝計算量」が誤り。選択肢4は「追加メモリを使わない」が誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 最悪もO(n log n)保証・安定 |
| 2 | ✓ | 最悪O(n log n)保証・安定 |
| 3 | ✗ | 安定性は同値の順番の保持 |
| 4 | ✗ | 追加メモリが必要 |
まとめ
押さえどころ
- 🔴 クイックソート ＝ 平均O(n log n)で実用的に最速クラス、ただし最悪O(n²)。不安定。
- 🔴 2グループ ＝ O(n²)（バブル・選択・挿入）／O(n log n)（マージ・ヒープ・クイック）。
- 🟡 安定性とマージソート ＝ 安定＝同値の順番が保たれる。マージソートは最悪O(n log n)保証・安定（追加メモリ要）。
次に学ぶ
- 配列・リスト ── ソートが並べ替える対象になる基本データ構造。データの持ち方とソートの相性がつながる。
- 計算量（オーダー） ── O(n²)とO(n log n)の差を正しく読む考え方。ソートの速さ比べの土台になる。
執筆: SikakuQuest編集部