挿入ソートの対象試験と出題頻度
「バブルソートは覚えたのに、挿入ソートとの違いを自分の言葉で説明できない」
整列アルゴリズムの学習でつまずきやすい地点がここです。
挿入ソートは基本情報技術者(FE)と応用情報技術者(AP)の科目Aで、配列の遷移や流れ図から手法名を選ばせる形式で繰り返し登場してきました。頻出度はB(標準)。
やや厄介なのは、正解になる問題と、誤答選択肢として置かれる問題の両方があること。判別軸を持たないまま本番に入ると、両方向で失点します。科目Bの擬似言語では、配列添字の読み取り練習としても格好の教材になります。
出題情報を確認する
基本情報技術者(FE), 応用情報技術者(AP)
★★★☆☆
ランクB(標準・覚えておくと有利)
挿入ソート(基本挿入法)の定義
過去問を解いていると、同じ手法が「基本挿入法」「単純挿入整列法」と別名で書かれていて手が止まることがあります。AP(ソフトウェア開発技術者)平成19年春 問11 の選択肢表記は「単純挿入法」でした。
いずれも英語名 Insertion Sort を指す同一の手法で、交換法(バブルソート)・選択法と並ぶ基本3ソートの一つ。IPAの問題文では英語名より日本語名で示されるのが通例です。まず定義を固めましょう。
挿入ソートとは、
「取り出した要素を整列済み部分の正しい位置に挿入していく整列法」
です。
すでに背の順で並んだ本棚に、新しい1冊を差し込む作業を思い浮かべてみてください。差し込む場所を右から順に探し、行き先が決まるまで本を1冊ずつ右へずらし、空いたすき間に新しい1冊を入れる。
この「ずらして差し込む」動作の繰り返しが挿入ソートの正体で、整列手法全体の位置づけは整列アルゴリズム(ソート)の比較表で確認できます。
📊 挿入ソートの基本情報
| 項目 | 内容 |
|---|---|
| 英語名 | Insertion Sort |
| 試験での別名 | 基本挿入法/単純挿入法/単純挿入整列法 |
| 要素の動き | シフト(ずらし)+挿入。隣接交換ではない |
| 平均・最悪計算量 | O(n²)(比較回数の最大は n(n-1)/2 回) |
| 最良計算量 | O(n)(整列済みなら比較 n-1 回) |
| 安定性・作業領域 | 安定(同値の順序を保つ)/退避用の1変数のみ |
解説:シフトして挿入する仕組みを1パスずつ追う
1パスの動きを4ステップで追う
挿入ソートの1回分の処理は、4つの動作に分解できます。
配列 [3, 5, 8 | 1](縦線の左が整列済み)を例に見てください。
挿入ソート1パスの処理ステップ
tmp ← 1
8 > 1 ?
[3, _, 5, 8]
[1, 3, 5, 8]
①→④の順に進む。③のシフトが挿入ソートの核で、バブルソートの「隣接交換」とは別物
注目すべきは③。
バブルソートは2要素の値を入れ替えますが、挿入ソートは大きい要素を1つずつ右へずらすだけで、値の入れ替えは発生しません。
退避した tmp が最後に1回だけ書き戻される点も特徴。擬似言語(科目B形式)で書くと次のようになります。
○insertionSort(整数型の配列: data)
整数型: i, j, tmp
for (i を 2 から dataの要素数 まで 1 ずつ増やす)
tmp ← data[i] /* ①未整列の先頭を退避 */
j ← i
while (j > 1 かつ data[j - 1] > tmp) /* ★着目:この2条件 */
data[j] ← data[j - 1] /* ③1つ右へシフト */
j ← j - 1
endwhile
data[j] ← tmp /* ④すき間に挿入 */
endfor
内側ループの条件は2つを「かつ」で結んだ形です。
j > 1 は配列の先頭を突き抜けないための番兵、data[j-1] > tmp は「まだ左の要素のほうが大きい=もっと左へ進める」の判定。どちらか一方が偽になった時点でループを抜け、その位置が挿入先になります。
配列(4, 1, 3, 2)を最後までトレースする
本番と同じ見え方で覚えるため、FE 平成14年春 午前 問14 で実際に示された数の並び (4, 1, 3, 2) を使います。
先頭の1要素は「すでに整列済み」とみなすのが出発点。
以降は未整列部分の先頭を1つずつ取り出していきます。
📊 (4, 1, 3, 2) の整列過程トレース表
| 回 | 取り出す要素 | 整列済み部分 | 未整列部分 | 比較回数 | 操作後の配列 |
|---|---|---|---|---|---|
| 初期 | — | 4 | 1, 3, 2 | — | 4, 1, 3, 2 |
| 1回目 | 1 | 4 | 3, 2 | 1回 | 1, 4, 3, 2 |
| 2回目 | 3 | 1, 4 | 2 | 2回 | 1, 3, 4, 2 |
| 3回目 | 2 | 1, 3, 4 | — | 3回 | 1, 2, 3, 4 |
| 比較回数の合計 | 6回 | 整列完了 | |||
表の読み方は、緑のセル(整列済み部分)が1回ごとに左から1要素分ずつ伸びていく点に置いてください。
3回目で取り出した 2 は、4 → 3 と2回ずらしてから3番目のすき間へ入り、比較は3回。要素数 n=4 の配列は必ず n-1 回、つまり3パスで完了します。
計算量:最悪O(n²)・最良O(n)になる理由
挿入ソートの計算量は、データの並び方で大きく表情を変えます。
逆順に並んだ配列では毎回のパスで整列済み部分を先頭まで見に行くため、比較回数は 1+2+…+(n-1) = n(n-1)/2 回。n=4 なら6回で、オーダーは O(n²) となります。
反対にすでに昇順なら、各パスの1回目の比較で「ずらす必要なし」と判定でき、比較は n-1 回だけ。n=4 では3回、オーダーは O(n) に落ちます。O記法そのものの意味はオーダー記法(計算量)で確認してください。
n=4 の実数値で最悪/最良を見比べる
1回+2回+3回=6回
n(n-1)/2 → O(n²)
1回+1回+1回=3回
n-1 → O(n)
AP(ソフトウェア開発技術者)平成20年秋 問11 は右側だけを問う設問
実務で数万件のソートを自前実装する場面はほぼなく、標準ライブラリに任せるのが常識です。
ただしPythonのTimSortやJavaの Arrays.sort は、分割された数十件規模の部分配列に対して内部で挿入ソートを呼び出しています。
「小規模データとほぼ整列済みデータなら挿入ソートが最速」という性質が、現代の高速ソートの土台になっているわけです。
なお、間隔を空けた挿入ソートを繰り返すシェルソートも、この性質を利用した改良版にあたります。
📝 ポイント整理
・本質は「交換」ではなくシフト(ずらし)+挿入
・(4, 1, 3, 2) は3パス・比較6回で 1, 2, 3, 4 に到達
・最悪 O(n²)/最良 O(n)、安定で追加メモリはほぼ不要
・擬似言語の要は内側ループ条件 j > 1 かつ data[j-1] > tmp
試験ではこう出る!出題パターンとひっかけ対策
出題は大きく3系統。どの形で来ても問われているのは「シフトして挿入する手法かどうか」の一点に集約されます。
挿入ソートが関与した過去問実績を見る(6件)
FE 平成14年春 午前 問14:数の並び (4, 1, 3, 2) の入替え過程から整列アルゴリズム名を問う。正解ウ=挿入ソート。トレース型の原型
AP(ソフトウェア開発技術者)平成19年春 午前 問11:比較回数が最悪 O(n²)、最良 O(n) となる整列法。正解ウ=単純挿入法
AP(ソフトウェア開発技術者)平成20年秋 午前 問11:昇順に整列済みのn個のデータを単純挿入整列法で再整列する際の比較回数のオーダ。正解ア=n
AP 令和4年秋 午前 問6:流れ図から整列アルゴリズムを特定。正解エ=バブルソートで、挿入ソートは誤答選択肢ウ
AP 令和5年秋 午前 問6:状態0〜Nの推移から手法を特定。正解ウ=バブルソートで、挿入ソートは誤答選択肢イ
FE 令和8年度 科目A 問2:クイックソートの説明を選ぶ問題。正解ウ。挿入ソートの説明文が誤答選択肢アに配置
📝 IPA試験での出題パターン
パターン1:トレース特定型
配列の状態推移や流れ図から手法名を選ぶ(FE H14春 問14/AP R4秋 問6/AP R5秋 問6)。挿入ソートは正解側と誤答側の両方に置かれる
パターン2:説明文選択型
4手法の説明文が並ぶ形式(FE 令和8年度 科目A 問2)。挿入ソートのキーワードは「整列済みの正しい位置に挿入・追加」
パターン3:計算量型
最悪 O(n²)・最良 O(n) の非対称性を突く形式(AP H19春 問11/AP H20秋 問11)。「整列済みデータを再整列したら?」は挿入ソート固有の問い方
3系統いずれも、動きの言語化と最良ケースの数値を持っていれば選択肢を2つまで絞れます。
誤答選択肢は他手法の説明文とほぼ同型で並びます。左列が出たら即座に正体を思い出してください。
⚠️ ひっかけ早見表
| 誤答の値・選択肢 | その正体 |
|---|---|
| 隣り合ったデータを比較して交換 | バブルソート(基本交換法)の説明文 |
| 最小値を求め、次に残りの最小値 | 選択ソート(基本選択法)の説明文 |
| 比較回数を一律 O(n²) と即答 | 「最良」「整列済み」なら O(n) 側 |
| 末尾から順に確定していく推移 | バブルソートの挙動。挿入は先頭側 |
📝 試験区分別の対策方針
・FE科目A:トレース特定型と説明文選択型を確実に取る
・FE科目B:擬似言語の内側ループ条件で添字操作を練習
・AP:最悪O(n²)と最良O(n)の非対称性を最優先で暗記
トレース1行目で見分ける:挿入ソート・バブルソート・選択ソートの3秒判別法
ログを時刻順に並べ直す、日次バッチで前日分の追加レコードだけを既存の整列済みリストへ差し込む。
実務でもこうした処理は頻繁に出てきます。全件を並べ直す実装から「追加分だけ差し込む」設計に変えて処理時間が桁で改善した経験があり、挿入ソートの発想は性能設計にそのまま効いてきました。
試験で3手法を見分ける軸は2つだけ。1パス後に確定するのが配列のどちら端か、そして値が隣とだけ動くか離れた位置へ飛ぶか。
この2軸で下表のように整理できます。
📊 3ソート判別マトリクス(例:4, 1, 3, 2 の1パス後)
| 手法 | 1パス後に確定する側 | 値の動き方 | トレース1行目の特徴 | 別名 | 安定性 |
|---|---|---|---|---|---|
| 挿入ソート | 先頭側(整列済みが左へ伸びる) | 1要素を退避し、大きい要素を右へシフト | 先頭2要素だけが整う(1, 4, 3, 2) | 基本挿入法/単純挿入整列法 | 安定 |
| バブルソート | 末尾側(最大値が右端に確定) | 隣同士の2要素を交換 | 末尾に最大値が来る(1, 3, 2, 4) | 基本交換法/隣接交換法 | 安定 |
| 選択ソート | 先頭側(最小値が左端に確定) | 離れた最小値を探して先頭と交換 | この例では挿入と同形(1, 4, 3, 2) | 基本選択法 | 不安定 |
末尾に大きい値が寄っていく推移ならバブルソート(基本交換法)で確定。
AP 令和5年秋 問6 の公式解説も「末尾から確定するなら [2] → [1, 2] → [1, 2, 6] のはず」という論法で挿入ソートを否定しました。
難所は挿入ソートと選択ソートの区別です。上表のとおり1行目が同じ形になるケースがあるため、その場合は2行目を見てください。
(4, 1, 3, 2) なら挿入ソートは 1, 3, 4, 2 で止まり、選択ソートは最小値2を先頭から2番目へ持ってきて 1, 2, 3, 4 に到達します。
覚え方はシンプルに、選択は最小値を探しに行く、挿入は取り出した1つを差し込むだけ。
【確認テスト】挿入ソートの理解度チェック
Q. 挿入ソート(基本挿入法)の説明として、最も適切なものはどれでしょうか?
- A. 隣り合った要素を比較し、順序が逆であれば交換する操作を繰り返して整列する。
- B. 未整列部分の中から最小値を探し出し、未整列部分の先頭要素と交換することを繰り返して整列する。
- C. 未整列部分の先頭から要素を取り出し、整列済み部分の順序関係を保つよう挿入することを繰り返して整列する。
正解と解説を見る
正解:C
解説:
Cは「取り出す」と「挿入する」の2動作で構成されており、FE 平成14年春 問14 の公式解説にある定義と一致します。整列済み部分の順序を崩さない位置へ差し込むため、同値の要素の前後関係も保たれる(安定な整列法)。
Aが不正解の理由:隣接要素の交換だけで進むのはバブルソート(基本交換法)。AP 令和4年秋 問6 の正解根拠そのままの文で、最も引っかかりやすい選択肢です。
Bが不正解の理由:未整列部分を走査して最小値を探すのは選択ソート(基本選択法)。先頭側から確定する点が共通するため混同しやすいものの、挿入ソートは最小値を探しに行きません。
補足:最良ケースの比較回数が n-1 回=O(n) になるのは、基本3ソートのうちCの挿入ソートだけ。AP 平成19年春 問11・平成20年秋 問11 はこの1点を突いた設問でした。
関連用語ネットワークと次に学ぶ手法
挿入ソートを起点に知識を広げるなら、前提・関連・発展の3方向で押さえると定着が早くなります。
📊 関連用語マップ
| カテゴリ | 関連用語 |
|---|---|
| 前提知識 | データ構造(配列・リスト)/配列の添字操作 |
| 関連用語 | バブルソート・選択ソート(判別軸で整理)/2分探索法(整列済みが前提の探索) |
| 発展 | シェルソート(挿入ソートの改良版)/クイックソート/ヒープソート |