クイックソートとは（全体像）
クイックソートとは、基準となる値（ピボット）を1つ選び、それより小さいデータと、大きいデータの2つに分ける。さらに、それぞれのグループでも同じことをくり返して、並べ替える方法のことだ。
背の順に並ぶときをイメージしよう。基準の1人を決めて、それより背が低い人・高い人に分ける。さらに各グループでも基準を決めて分ける。これをくり返すと、すばやく順番がそろう。
ここで一番のポイント。クイックソートは、平均ではとても速い（O(n log n)）。バブルソート（O(n²)）より、ずっと速い。だから、多くのプログラミング言語で、標準のソートに使われている。
詳しく：平均は速いが、最悪はO(n²)
ここが心臓部。速さのポイントを押さえよう。
クイックソートのポイント
| 項目 | やさしい意味 |
|---|---|
| 方式 | 基準値（ピボット）で、小さい組・大きい組に分けてくり返す |
| 平均の速さ | 速い（O(n log n)）。バブルソートより速い |
| 最悪の速さ | 遅くなることもある（O(n²)） |
| 実用性 | 多くの言語で標準的に使われる |
クイックソートは、平均では速い（O(n log n)）。これが大きな強みで、実用上の標準になっている。
ただし、つねに速いとは限らない。データの偏り方によっては、最悪のとき、O(n²)まで遅くなることがある。「クイックソートは、常にO(n log n)で速い」と思い込むと誤りになる。平均は速いが、最悪はO(n²)、と押さえよう。
わかりやすく言い換えると
身近なたとえで整理しよう。
クイックソートは、「基準の1人を決めて、背が低い組・高い組に分け、さらに各組でも分けていく」イメージ。どんどん細かく分かれて、すばやく並ぶ。つまり、分けてから、それぞれを並べる考え方だ。
「平均は速い」というのは、ふつうのデータなら、バブルソートよりずっと速いこと。だから標準的に使われる。
「最悪はO(n²)」というのは、データの偏り方によっては、遅くなることもあること。要するに、つねに最速、とは限らない。
試験のツボ
🔴 一番出る：クイックソートの仕組み
①基準値（ピボット）で、小さい組・大きい組に分ける
②さらに各組でもくり返して、並べ替える
🔴 次に出る：平均は速い
①平均では速い（O(n log n)）
②バブルソート（O(n²)）より速く、標準的に使われる
🟡 押さえると安定：最悪はO(n²)
①データの偏り方によっては、最悪はO(n²)
②「常にO(n log n)で速い」とは限らない
よくある間違い
①「クイックソートは、どんなときも必ずO(n log n)で速い」→ ✗ 平均は速い（O(n log n）が、最悪のときはO(n²)まで遅くなることがある。
②「クイックソートは、バブルソートより遅い」→ ✗ 平均では、クイックソートのほうがバブルソート（O(n²)）より速い。
③「クイックソートは、隣り合うデータを比べて入れ替えるだけだ」→ ✗ 隣どうしを比べるのはバブルソート。クイックソートは、基準値で分けてくり返す。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（クイックソートの仕組み）
クイックソートに関する次の記述のうち、最も適切なものはどれか。
- 社員の出退勤を記録して、毎月の給与を計算するためのしくみである
- 取引先へ毎月の請求書を郵送する、決まった事務作業のことを指す
- 完成したシステムを宣伝して、より多く売るための広告活動である
- 基準値で、小さい組と大きい組に分けて並べ替えていく方法である
解答は 4 だぱん。
クイックソートは、基準値（ピボット）で、小さい組と大きい組に分けて並べ替える方法なんだぱん。さらに各組でもくり返すんだぱん。
選択肢1は給与計算、選択肢2は請求書の事務、選択肢3は広告で、どれも違うぱん。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 給与計算のしくみではない |
| 2 | ✗ | 請求書の事務の話 |
| 3 | ✗ | 広告活動ではない |
| 4 | ✓ | 基準値で分けて並べ替えるで正しい |
オリジナル問題2（平均は速い）
クイックソートの速さに関する次の記述のうち、最も適切なものはどれか。
- 社員の給与の計算しだいで、速さが決まるとされているものだ
- 平均では速く、O(n log n)でバブルソートより速い
- 取引先への請求書の枚数しだいで、速さが決まるとされている
- 平均では、バブルソートよりずっと遅いものだとされている
解答は 2 だぱん。
クイックソートは、平均では速く（O(n log n)）、バブルソートより速いんだぱん。だから多くの言語で標準的に使われるんだぱん。
選択肢1の給与、選択肢3の請求書、選択肢4の「ずっと遅い」は、いずれも違うぱん。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 給与計算で決まるのではない |
| 2 | ✓ | 平均は速くバブルより速いで正しい |
| 3 | ✗ | 請求書の枚数で決まるのではない |
| 4 | ✗ | バブルソートより速い |
オリジナル問題3（最悪はO(n²)）
クイックソートの最悪の場合に関する次の記述のうち、最も適切なものはどれか。
- データの偏り方によっては、最悪はO(n²)まで遅くなることがある
- どんなときも必ずO(n log n)で、最悪でも遅くならないとされる
- 社員の給与を計算するときだけ、最悪になるとされているものだ
- 取引先へ請求書を郵送するときだけ、最悪になるとされている
解答は 1 だぱん。
クイックソートは、データの偏り方によっては、最悪はO(n²)まで遅くなることがあるんだぱん。「常に速い」とまちがえないようにするといいぱん。
選択肢2の「必ずO(n log n)」、選択肢3の給与、選択肢4の請求書は、いずれも違うぱん。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | 最悪はO(n²)になることがあるで正しい |
| 2 | ✗ | 最悪はO(n²)になることがある |
| 3 | ✗ | 給与計算のときではない |
| 4 | ✗ | 請求書の郵送のときではない |
まとめ
押さえどころ
- 🔴 クイックソート ＝ 基準値（ピボット）で、小さい組・大きい組に分けてくり返す、速い並べ替え方法。
- 🔴 平均は速い ＝ 平均ではO(n log n)で、バブルソート（O(n²)）より速い。標準的に使われる。
- 🟡 最悪はO(n²) ＝ データの偏り方によっては遅くなる。常に速いとは限らない。
次に学ぶ
- バブルソート ── 隣どうしを比べて並べ替える方法。クイックソートと速さを比べると分かりやすい。
- 計算量 ── アルゴリズムの速さの目安。平均と最悪で変わることもある。
執筆: SikakuQuest編集部