対象試験と出題頻度
クイックソートは、基本情報技術者・応用情報技術者で出題されるテーマです。
科目Aでは整列アルゴリズムの説明を選ぶ定義問題や分割途中の配列状態を問うトレース問題、科目Bでは擬似言語による実装の読解問題として出題されます。
FE H30秋期 午前問6、FE R5年度 科目B 問3、AP R5春期 午前問7、AP R元秋期 午前問8など、出題実績は豊富です。
詳細をクリックして確認
基本情報技術者
応用情報技術者
★★★☆☆
ランクB（標準）覚えておくと有利
用語の定義
情報処理試験を勉強していると、「ソートの種類が多すぎて、クイックソートと他の整列法の違いがよくわからない」と混乱しがちです。
クイックソート（Quick Sort）とは、一言で言うと
「基準値（ピボット）を選び、それより小さい値と大きい値のグループに分割する操作を再帰的に繰り返して整列するアルゴリズム」
のことです。
イメージとしては、「テストの点数で『平均点より上・下』にクラスを分け、さらに各クラス内でも同じ分け方を繰り返して、最終的に全員を成績順に並べる」こと。
1回の分割では完全な順序にならなくても、分割を繰り返すたびにグループが小さくなり、最終的に全体が整列されます。
この「分けて統治する」考え方は分割統治法（Divide and Conquer）と呼ばれ、クイックソートはその代表格です。
📊 クイックソートの基本情報
| 項目 | 内容 |
|---|---|
| 英語名 | Quick Sort |
| 分類 | 分割統治法（Divide and Conquer）を用いた整列 |
| 平均計算量 | O(n log n) |
| 最悪計算量 | O(n²)（既にソート済みのデータでピボット選択が偏る場合） |
| 安定性 | 不安定ソート（同じ値の要素の順序が保たれない場合がある） |
詳細解説
整列アルゴリズムには、隣接要素を比較するバブルソートのような単純な手法から、データ構造を活用するヒープソートまで多様な種類があります。
クイックソートは、その中でも平均的な処理速度が最も速い部類に入るため、実務のプログラミングで広く採用されています。
動作の仕組み
配列の中から基準値（ピボット）を1つ選びます。選び方は実装によって異なりますが、試験では「配列の左端の値」とする問題がほとんどです。
次に、ピボットより小さい値を左側、大きい値を右側に振り分けます。この1回の操作を「分割（パーティション）」と呼びます。分割後、左右それぞれのグループに対して同じ操作を再帰的に繰り返すと、最終的に全要素が昇順に並びます。
▶ 図解：クイックソートの動作例 [5, 3, 8, 1, 7]（クリックで展開）
【1回目の分割】ピボット＝5
初期状態：53817
5より小さい → 31 5より大きい → 87
分割結果：31587
→ 5の位置が確定。左グループ[3,1]と右グループ[8,7]を再帰処理
【2回目の分割】左グループ [3, 1] ピボット＝3 ／ 右グループ [8, 7] ピボット＝8
左：3より小さい→1、3より大きい→なし → [1, 3] 確定
右：8より小さい→7、8より大きい→なし → [7, 8] 確定
【結果】
整列完了：13578
▶ 擬似コード：クイックソートの実装（クリックで展開）
IPAの科目Bで出題される擬似言語に近い形で記述します。
○ quickSort(整数型の配列: A, 整数型: left, 整数型: right)
if (left < right)
整数型: pivotIndex ← partition(A, left, right)
quickSort(A, left, pivotIndex - 1) // 左グループを再帰処理
quickSort(A, pivotIndex + 1, right) // 右グループを再帰処理
endif
○ partition(整数型の配列: A, 整数型: left, 整数型: right)
整数型: pivot ← A[left]
整数型: i ← left
整数型: j ← right
while (true)
while (A[i] < pivot)
i ← i + 1
endwhile
while (A[j] > pivot)
j ← j - 1
endwhile
if (i >= j)
return j
endif
A[i] と A[j] を交換
i ← i + 1
j ← j - 1
endwhilepartition関数が「分割」を担当し、quickSort関数が「再帰」を担当します。partition内ではピボットを基準に左右から走査し、交換すべき要素を見つけて入れ替えます。iとjが交差したら分割完了です。
計算量とピボット選択の関係
クイックソートの平均計算量はO(n log n)で、実用的なソートアルゴリズムの中で最速クラスです。
ただし、ピボットの選び方によっては性能が大きく変動します。毎回の分割でデータが均等に二分されるのが理想ですが、既にソート済みのデータで常に左端をピボットに選ぶと、片方のグループにデータが偏り続け、分割がn−1回必要になります。この最悪ケースでは計算量がO(n²)に退化します。
他の整列アルゴリズムとの比較
| アルゴリズム | 動作の特徴 | 平均 | 最悪 | 安定 |
|---|---|---|---|---|
| クイックソート | ピボットで分割を再帰的に繰り返す | O(n log n) | O(n²) | × |
| マージソート | データを半分に分割し、整列しながら統合する | O(n log n) | O(n log n) | ○ |
| ヒープソート | 未整列部分を順序木（ヒープ）にし、最小値を取り出す | O(n log n) | O(n log n) | × |
| バブルソート | 隣り合う要素を比較・交換する | O(n²) | O(n²) | ○ |
| シェルソート | 一定間隔おきの部分列を整列し、間隔を詰めていく | O(n^1.25)～ | O(n²) | × |
ここだけは確実に押さえてください。クイックソートの識別キーワードは「基準値（ピボット）」「分割」「再帰」の3語です。マージソートは「分割＋統合（マージ）」、ヒープソートは「順序木」、バブルソートは「隣接要素の交換」と整理すれば、選択肢で迷うことはありません。
では、この用語が試験でどのように出題されるか見ていきましょう。
💡 クイックソートの核心を3行で
・ピボットを基準にデータを2グループに分割し、再帰的に整列する分割統治法のアルゴリズム
・平均計算量は O(n log n) だが、ピボット選択が偏ると最悪 O(n²) に退化する
・マージソートとの違いは「分割時に整列する（クイック）」vs「統合時に整列する（マージ）」
試験ではこう出る！
クイックソートは、整列アルゴリズムの定義を選ぶ問題、分割後の配列状態を問うトレース問題、そして科目Bの擬似言語読解と、出題のバリエーションが豊富です。
出題パターンは大きく3つに分かれます。
📊 過去問での出題実績
| 試験回 | 出題内容 | 問われたポイント |
|---|---|---|
| FE H30秋期 午前 問6 |
4つのソートアルゴリズムの説明文からクイックソートを選ぶ問題。 | ・「基準値で分割を繰り返す」が正解 ・挿入ソート・選択ソート・バブルソートがひっかけ |
| FE R5年度 科目B 問3 |
擬似言語で書かれたクイックソートのプログラムを読み取り、特定時点での配列の出力値を答える問題。 | ・partition処理のトレース力 ・再帰呼び出しの順序を正確に追えるか |
| AP R5春期 午前 問7 |
配列 [2,3,5,4,1] に対して2回目の分割が終わった状態を選ぶ問題。 | ・左端をピボットとして分割を手順通りトレースできるか ・正解は [1,2,3,5,4] |
| AP R元秋期 午前 問8 |
「分割統治を利用した整列法」を選ぶ問題。 | ・クイックソート＝分割統治法という知識の即答問題 ・基数ソート・選択ソート・挿入ソートがひっかけ |
📝 IPA試験での出題パターン
パターン1：「クイックソートの説明を選べ」
4つの整列法の説明文が並び、該当するものを選ぶ定義問題。「基準値」「小さい値と大きい値に分割」「繰り返す」が含まれる選択肢を選べば正解。
パターン2：「n回目の分割後の配列状態を選べ」
具体的な配列とピボットの選び方が与えられ、指定回数の分割後の状態を答えるトレース問題。AP R5春期 問7が典型例。ピボットの選択ルール（左端・中央値など）を問題文から正確に読み取ることが重要。
パターン3：「擬似言語のクイックソートをトレースせよ」（科目B）
FE R5年度 科目B 問3のように、再帰関数とpartition関数が組み合わさったプログラムを読み解く問題。再帰の呼び出し順序と各変数の値の変化を丁寧に追う必要がある。
科目Aでは「基準値で分割＋再帰＝クイックソート」「分割統治法＝クイックソート or マージソート」と即答できれば十分です。科目Bのトレース問題は、3〜5要素の小さい配列で手を動かして練習しておくのが最短ルートです。
【確認テスト】理解度チェック
ここまでの内容を理解できたか、簡単なクイズで確認してみましょう。
Q. クイックソートの説明として、最も適切なものはどれでしょうか？
- A. 隣り合う要素を比較して、大小の順が逆であれば入れ替えるという操作を繰り返す。
- B. 未整列の部分を順序木にし、そこから最小値を取り出して整列済みの部分に移す操作を繰り返す。
- C. 適当な基準値を選び、それより小さな値のグループと大きな値のグループにデータを分割する操作を再帰的に繰り返す。
正解と解説を見る
正解：C
解説：
クイックソートは、基準値（ピボット）を選んでデータを2グループに分割し、各グループに対して再帰的に同じ操作を繰り返す分割統治型の整列アルゴリズムです。「基準値」「分割」「再帰」の3語が判断基準になります。
選択肢Aはバブルソート（基本交換法）の説明です。隣接する要素同士の比較・交換で整列する単純な手法であり、分割やピボットの概念はありません。選択肢Bはヒープソートの説明です。データをヒープ（順序木）というデータ構造に格納し、最小値（または最大値）を順に取り出す手法であり、基準値による分割は行いません。
よくある質問（FAQ）
Q. クイックソートとマージソートはどちらも分割統治法ですが、何が違いますか？
整列が行われるタイミングが異なります。クイックソートは「分割するとき」にピボットを基準にデータを振り分けるため、分割の段階で大小関係が整理されます。一方、マージソートは分割時には単純に半分に切るだけで、「統合（マージ）するとき」に大小比較を行って整列します。また、マージソートは最悪でもO(n log n)を保証しますが、別途作業用の配列が必要になるという違いもあります。
Q. ピボットの選び方で最悪ケースを回避する方法はありますか？
あります。代表的な方法は「median-of-three（三値の中央値）」で、配列の先頭・中央・末尾の3つの値の中央値をピボットにする手法です。これにより、既にソート済みのデータでも分割の偏りが緩和され、最悪ケースに陥る確率が大幅に下がります。ただし、IPA試験ではピボットの選び方は問題文で指定されるため、この知識が直接問われることはありません。参考程度で構いません。
Q. クイックソートが不安定ソートだと、実務でどんな問題がありますか？
不安定ソートでは、同じキーを持つレコードの相対的な順序が整列後に変わる場合があります。たとえば「同じ得点の生徒を名前順に並べておいた後に得点順で再ソートする」とき、不安定ソートだと同点の生徒の名前順が崩れます。こうしたケースでは安定ソートであるマージソートが選ばれます。多くのプログラミング言語の標準ライブラリは、安定性を保証するためにマージソートやTimSort（マージソート＋挿入ソートの混合）を採用しています。
Q. 科目Bで再帰のトレースが苦手です。コツはありますか？
「コールスタック（呼び出しの積み重ね）」を紙に書き出すのが最も確実な方法です。再帰呼び出しが発生するたびに、現在の関数の引数と局所変数をメモして「一旦保留」し、新しい呼び出しに進みます。呼び出し先から戻ってきたら保留メモを復元して処理を再開する、という手順を機械的に繰り返せば、再帰の動作を正確に追えます。最初は3要素の配列で練習し、慣れたら5要素に挑戦してください。
