対象試験と出題頻度
整列アルゴリズム（ソート）は、基本情報技術者・応用情報技術者で出題されるテーマです。
科目Aでは「ソート手法の説明を選べ」「整列過程からアルゴリズム名を特定せよ」という形式が定番で、科目Bではクイックソートやマージソートの擬似言語プログラムをトレースする問題が繰り返し出題されています。
詳細をクリックして確認
基本情報技術者
応用情報技術者
★★★☆☆
ランクB（標準）覚えておくと有利
用語の定義
情報処理試験を勉強していると、「バブルソートとかクイックソートとか種類が多すぎて整理できない…」と混乱しがちです。
整列アルゴリズム（ソート）とは、一言で言うと
「データの集まりを、ある基準に従って昇順または降順に並べ替える手順」
のことです。
イメージとしては、「バラバラに並んだ生徒を、身長順に整列させる体育の先生のやり方」です。
先生によって「端から順に隣の人と比べて入れ替える」派もいれば、「一番小さい人を見つけて先頭に持ってくる」派もいます。どのやり方でも最終的に身長順に並ぶのは同じですが、人数が増えたときの効率がまるで違います。
これがソートアルゴリズムの世界です。
📊 整列アルゴリズム（ソート）の基本情報
| 項目 | 内容 |
|---|---|
| 英語名 | Sorting Algorithm |
| IPAシラバス用語例 | 選択ソート、バブルソート、挿入ソート、シェルソート、クイックソート、マージソート、ヒープソート |
| 分類のポイント | 「比較の仕方」と「平均計算量」で整理するのが最短ルート |
詳細解説
ソートの種類は多いですが、試験で問われるのは「各手法が何を比較・交換しているか」と「計算量（オーダー）」の2点に集中しています。
ここでは7つのソートを、動きの特徴と計算量で整理します。
基本の3手法（計算量 O(n²)）
データ件数 n が増えると処理時間が n の2乗に比例して増えるグループです。仕組みが単純な反面、大量データには不向きです。
▶ バブルソート（基本交換法）の動き（クリックで展開）
隣り合う2つの要素を比較し、順序が逆なら交換する操作を端から端まで繰り返します。1回走査するごとに、未整列部分の最大値（または最小値）が確定していきます。
【例】配列 [5, 3, 8, 1] を昇順に整列
1回目：[5, 3, 8, 1] → [3, 5, 8, 1] → [3, 5, 8, 1] → [3, 5, 1, 8]
2回目：[3, 5, 1, 8] → [3, 5, 1, 8] → [3, 1, 5, 8]
3回目：[3, 1, 5, 8] → [1, 3, 5, 8] → 整列完了
赤字が比較対象、青字が確定した要素です。「泡（バブル）が浮き上がるように」最大値が末尾に集まることからこの名前がつきました。
▶ 選択ソート（基本選択法）の動き（クリックで展開）
未整列部分の中から最小値を探し出し、先頭の要素と交換する操作を繰り返します。毎回「選んで」先頭に置くのが名前の由来です。
【例】配列 [5, 3, 8, 1] を昇順に整列
1回目：最小値 1 を先頭と交換 → [1, 3, 8, 5]
2回目：残り [3, 8, 5] の最小値 3 はそのまま → [1, 3, 8, 5]
3回目：残り [8, 5] の最小値 5 を交換 → [1, 3, 5, 8] → 整列完了
▶ 挿入ソート（基本挿入法）の動き（クリックで展開）
未整列部分の先頭要素を取り出し、整列済み部分の正しい位置に差し込む操作を繰り返します。トランプの手札を左から順に正しい場所に入れていくイメージです。
【例】配列 [5, 3, 8, 1] を昇順に整列
初期：[5 | 3, 8, 1] ※5を整列済みとする
1回目：3 を5の前に挿入 → [3, 5 | 8, 1]
2回目：8 は5の後ろでOK → [3, 5, 8 | 1]
3回目：1 を3の前に挿入 → [1, 3, 5, 8] → 整列完了
高速な4手法（計算量 O(n log n) が期待できる）
データを分割・統合したり、木構造を利用することで計算量を大幅に抑えたグループです。
▶ クイックソートの動き（クリックで展開）
基準値（ピボット）を1つ選び、「基準値より小さいグループ」と「大きいグループ」に分割する操作を再帰的に繰り返します。平均計算量は O(n log n) ですが、最悪時（既にほぼ整列済みのデータ等）は O(n²) に劣化します。
【概要】配列 [3, 5, 9, 6, 1, 2]
基準値 5 を選択
→ 小さいグループ [3, 1, 2] | 大きいグループ [9, 6]
→ それぞれのグループ内でさらに基準値を選んで分割…
→ 最終的に [1, 2, 3, 5, 6, 9]
名前の通り「平均的に最も速い」ソートとして知られ、実務のプログラミング言語の標準ライブラリでも広く採用されています。
▶ マージソートの動き（クリックで展開）
配列を半分ずつに分割し続け、要素が1つになったら隣同士を整列しながら併合（マージ）していきます。計算量は最悪でも O(n log n) で安定しています。
【概要】配列 [5, 3, 8, 1]
分割：[5, 3] [8, 1] → [5] [3] [8] [1]
併合：[3, 5] [1, 8] → [1, 3, 5, 8]
追加のメモリ領域が必要になるのが弱点ですが、データの偏りに左右されない安定した速度が強みです。
▶ ヒープソートの動き（クリックで展開）
データをヒープ木（親の値が子の値以上、または以下になる完全二分木）として構成し、根から最大値（または最小値）を取り出して整列済み領域に移す操作を繰り返します。計算量は最悪でも O(n log n) です。
追加メモリが不要な点が強みですが、実測速度ではクイックソートに劣ることが多いです。
▶ シェルソートの動き（クリックで展開）
挿入ソートの改良版です。最初は離れた間隔（ギャップ）で要素を取り出して部分列ごとに挿入ソートを行い、徐々に間隔を狭めて最終的にギャップ1の通常の挿入ソートで仕上げます。
事前にデータをおおまかに整えることで、最終段階の挿入ソートの交換回数が激減します。計算量はギャップの選び方に依存し、おおむね O(n^1.25)〜O(n^1.5) 程度です。
7種のソートアルゴリズム比較表
ここだけは確実に押さえてください。以下の比較表を丸ごと頭に入れれば、科目Aの選択問題は即答できます。
📊 ソートアルゴリズム7種 比較一覧
| 手法名 | 別名 | 平均計算量 | 最悪計算量 | 安定性 | 動きの特徴（一言） |
|---|---|---|---|---|---|
| バブルソート | 基本交換法 | O(n²) | O(n²) | 安定 | 隣同士を比較・交換 |
| 選択ソート | 基本選択法 | O(n²) | O(n²) | 不安定 | 最小値を探して先頭と交換 |
| 挿入ソート | 基本挿入法 | O(n²) | O(n²) | 安定 | 整列済み部分に正しい位置で挿入 |
| シェルソート | — | O(n^1.25)～ | O(n²) | 不安定 | 間隔を縮めながら挿入ソート |
| クイックソート | — | O(n log n) | O(n²) | 不安定 | 基準値で大小2グループに分割を再帰 |
| マージソート | — | O(n log n) | O(n log n) | 安定 | 分割→整列しながら併合 |
| ヒープソート | — | O(n log n) | O(n log n) | 不安定 | ヒープ木の根から最大/最小値を取り出す |
※「安定」とは、同じ値のデータが元の並び順を保ったまま整列されることを指します。
では、この用語が試験でどのように出題されるか見ていきましょう。
💡 整列アルゴリズムの核心を3行で
・O(n²) の基本3手法（バブル・選択・挿入）は「何を比較・交換するか」で区別する
・O(n log n) の高速4手法は「分割の仕方」と「最悪計算量が劣化するか」で区別する
・クイックソートだけ最悪 O(n²) になる点がひっかけの定番
試験ではこう出る！
整列アルゴリズムは、科目Aと科目Bの両方で繰り返し出題されているテーマです。
出題パターンは大きく3つに分かれます。
📊 過去問での出題実績
| 試験回 | 出題内容 | 問われたポイント |
|---|---|---|
| AP R5秋 午前 問6 |
データ列の整列過程を示し、使われた手法を問う問題。 | ・1回の走査で最大値が末尾に確定する動きからバブルソートを特定 ・クイックソートやヒープソートの説明がひっかけ |
| AP R4秋 午前 問6 |
流れ図を読んで整列手法を特定する問題。 | ・「隣接要素の比較・交換」をフローチャートから読み取れるか ・バブルソート（基本交換法）が正解 |
| FE H30秋 午前 問6 |
クイックソートの処理方法を説明した選択肢を選ぶ問題。 | ・「基準値で大小のグループに分割を繰り返す」が正解 ・挿入ソート、選択ソート、バブルソートの説明がひっかけ |
| AP H26秋 午前 問6 |
データ列の分割・併合の過程を図で示し、手法を問う問題。 | ・「分割→整列しながら併合」の流れからマージソートを特定 ・クイックソートとの混同に注意 |
| FE R5 科目B 問3 |
クイックソートの擬似言語プログラムを読みトレースする問題。 | ・基準値による分割と再帰呼び出しの流れを追えるか ・配列の添字の動きを正確にトレースする力が必要 |
📝 IPA試験での出題パターン
パターン1：「この整列方法は何か？」
データ列の変化の過程や流れ図を示し、4択からアルゴリズム名を選ぶ形式。「隣接要素の交換→バブル」「基準値で分割→クイック」「分割と併合→マージ」をキーワードで即判定する。
パターン2：「○○ソートの説明を選べ」
4つの手法の説明文が並び、指定された名前に該当するものを選ぶ形式。FE H30秋 問6のクイックソートが典型例。
パターン3：「擬似言語プログラムのトレース」（科目B）
FE R5 科目B 問3のように、ソートの擬似言語コードが示され、実行結果や途中状態を問う形式。クイックソートとマージソートが頻出。
試験ではここまででOKです。計算量の数学的な導出や安定性の証明まで問われることはないので、深追いは不要です。前述の比較表の内容を覚えていれば得点できます。
【確認テスト】理解度チェック
ここまでの内容を理解できたか、簡単なクイズで確認してみましょう。
Q. 整列アルゴリズムに関する説明として、最も適切なものはどれでしょうか？
- A. 未整列の部分をヒープ木として構成し、根から最大値を取り出して整列済み領域に移す操作を繰り返す手法をマージソートという。
- B. 適当な基準値を選び、それより小さな値のグループと大きな値のグループにデータを分割する操作を再帰的に繰り返す手法をクイックソートという。
- C. 隣り合ったデータを比較・交換し、小さな値を端へ移動させていく手法をクイックソートという。
正解と解説を見る
正解：B
解説：
クイックソートは、基準値（ピボット）を選んでデータを大小2つのグループに分割し、それぞれのグループ内で同じ操作を再帰的に繰り返す整列手法です。平均計算量 O(n log n) で、実用上最も高速なソートの一つです。
選択肢Aはヒープソートの説明です。ヒープ木の根から最大値を取り出す操作はヒープソート固有の仕組みであり、マージソートは「分割→整列しながら併合」する手法です。選択肢Cはバブルソート（基本交換法）の説明です。隣り合う要素の比較・交換はバブルソートの特徴であり、クイックソートの動きではありません。
よくある質問（FAQ）
Q. クイックソートの「最悪 O(n²)」はどんなときに起きますか？
既にほぼ昇順（または降順）に並んでいるデータに対して、先頭や末尾の要素をピボットに選んでしまった場合です。分割が偏り、毎回1つの要素しか切り離せなくなるため、計算量がバブルソートと同等にまで劣化します。実務では「ピボットをランダムに選ぶ」「先頭・中央・末尾の中央値を選ぶ」などの対策が取られます。
Q. 「安定なソート」と「不安定なソート」は試験で問われますか？
直接問われる頻度は低いですが、応用情報の午後問題で「同じキーのレコードの順序が保たれるか」を考慮させる出題がまれにあります。安定なのはバブル・挿入・マージの3つ、不安定なのは選択・シェル・クイック・ヒープの4つと覚えておけば十分です。
Q. 実務で使うプログラミング言語のソート関数は、どのアルゴリズムを使っていますか？
多くの言語はクイックソートとマージソートを組み合わせたハイブリッド方式を採用しています。Pythonの標準ソートは挿入ソートとマージソートを組み合わせた「TimSort」、JavaのArrays.sortはデータ型によってDual-Pivot QuicksortとTimSortを使い分けます。試験範囲ではこれらの詳細は問われないので、参考程度で構いません。
Q. 比較回数が n(n-1)/2 と出てきたらどのソートですか？
バブルソートの比較回数です。n個のデータに対して、1回目の走査で n-1 回、2回目で n-2 回…と比較するため、合計は (n-1)+(n-2)+…+1 = n(n-1)/2 になります。FE H13春 午前でもこの計算が出題されています。選択ソートも同じ比較回数ですが、試験で「n(n-1)/2」が問われたときはバブルソートが題材になることがほとんどです。
