整列アルゴリズムの仕組みとトレース：バブル・選択・挿入ソートの実戦解法

ソートの途中で、どの部分が整列済みになるのでしょうか？

この例では、バブルは末尾、選択は先頭から値が確定します。挿入ソートは整列済みの区間へ値を差し込みます。配列の変化をパスごとに追います。

3大基本整列アルゴリズムの比較と計算量

まず、3つの基本ソートの特徴・仕組み・計算量を一覧表で整理しましょう。

アルゴリズム名	和名（別名）	動作の基本アイデア	最悪計算量	最良計算量	特徴・着眼点
バブルソート	基本交換法	隣り合う要素を比較し、順序が逆なら交換。最大値が末尾に浮上。	O(n²)	O(n) (フラグ改善時)	各パスで末尾から値が確定。実装が極めて簡単。
選択ソート	基本選択法	未整列領域から「最小値」を探し、先頭要素と1回交換。	O(n²)	O(n²)	各パスで先頭から値が確定。交換回数が O(n) と最少。
挿入ソート	基本挿入法	未整列の先頭を取り出し、整列済領域の正しい位置に差し込む。	O(n²)	O(n) (初期整列時)	既に整列済みならO(n)。他方式との速度比較はデータや実装の条件による。

バブルソート（基本交換法）のトレース術

配列 A = [5, 3, 8, 4, 2] を昇順（小さい順）に並べ替えるバブルソートの手順を追跡します。

パスごとの配列の変化（末尾から確定する！）

実行フェーズ	配列の状態	確定した要素・処理内容
初期状態	[5, 3, 8, 4, 2]	未整列 (全5要素)
第1パス終了	[3, 5, 4, 2, \| 8]	最大値【8】が右端に移動して確定
第2パス終了	[3, 4, 2, \| 5, 8]	2番目に大きい【5】が確定
第3パス終了	[3, 2, \| 4, 5, 8]	【4】が確定
第4パス終了	[2, \| 3, 4, 5, 8]	【3】が確定し、自動的に全整列完了

【トレースの鉄則】：バブルソートは外側ループが 1 回回るごとに、「一番右端（末尾）に未整列領域の最大値が 1 つずつ確定」していきます。

問題で「第2パス終了時の配列はどれか」と問われたら、右端2つが昇順最大になっている選択肢を絞り込みましょう。

基本選択法（選択ソート）のトレース術

選択ソートは、未整列領域の中から「最小値」を探索し、未整列領域の先頭と交換します。

パスごとの配列の変化（先頭から確定する！）

実行フェーズ	配列の状態	最小値の探索と交換
初期状態	[5, 3, 8, 4, 2]	全要素から最小値【2】を発見 → A[0]の5と交換
第1パス終了	[2 \| 3, 8, 4, 5]	【2】が先頭に確定。残りから最小値【3】を発見
第2パス終了	[2, 3 \| 8, 4, 5]	【3】はすでに先頭なので自分と交換（確定）
第3パス終了	[2, 3, 4 \| 8, 5]	残りから最小値【4】を発見 → A[2]の8と交換
第4パス終了	[2, 3, 4, 5 \| 8]	残りから最小値【5】を発見 → A[3]の8と交換。整列完了

【トレースの鉄則】：選択ソートはバブルソートと逆で、「一番左端（先頭）から順に最小値が 1 つずつ確定」していきます。各パスでの交換回数が高々1回しかないのが特徴です。

実戦演習：挿入ソートの穴埋め問題

以下の擬似言語プログラムは、要素数 n の配列 A を基本挿入法によって昇順に整列する関数です。空欄に入る適切なコードを考えてみましょう。

text

○Sort(整数型の配列: A, 整数型: n)
  整数型: i, j, tmp
  for (i を 1 から n - 1 まで 1 ずつ増やす)
    tmp ← A[i]
    j ← i - 1
    while (j ≧ 0 and A[j] > tmp)
      A[j + 1] ← A[j]  // 要素を1つ右へシフト
      j ← j - 1
    endwhile
    【   a   】 ← tmp  // 空いた位置に値を挿入
  endfor

【空欄 a の選択肢】

A[j]
A[j + 1]
A[i]
A[i - 1]

解説と解答

正解：イ（A[j + 1]）

while ループの終了時、j は「tmp 以下の要素が見つかった位置」または -1 になっています。
したがって、tmp を挿入すべき正しい位置は、その 1 つ右側のインデックスである j + 1 です。A[j + 1] ← tmp とすることで、隙間に新しい値が正しく収まります。

挿入ソートのパスを一つずつ追う

添字0始まりのA＝[5,3,8,4,2]では、各パス後の状態は次のとおりです。

挿入する値	パス後の配列	整列済みの範囲
3	[3,5,8,4,2]	A[0]〜A[1]
8	[3,5,8,4,2]	A[0]〜A[2]
4	[3,4,5,8,2]	A[0]〜A[3]
2	[2,3,4,5,8]	全体

while終了時のjは、挿入位置そのものではなく、その一つ左です。最小値2を挿入するときはj＝−1となり、A[j＋1]＝A[0]へ戻します。

同じ値の順序を保つ「安定性」とコードの前提

同じキーのデータの元の順番を保つソートを安定と呼びます。隣接要素を「大きいときだけ」交換するバブルと、A[j]＞tmpのときだけずらす挿入は安定です。最小値と先頭を交換する通常の選択ソートは安定ではありません。

同じソート名でも、実装で動きや最良計算量が変わります。末尾確定はここでの左から右へ比較するバブルの例です。バブルの最良O(n)には、交換なしで終了する判定が必要です。

演習は添字0始まりです。whileのandを短絡評価する前提なら、j＝−1のときA[j]を読まずに終了します。その前提がない形式では、先にj≧0を確認し、内側で値を比較する構造に分けます。

まとめ：ソート問題を見分けるチェックシート

末尾から最大値が固まっていく＝バブルソート（基本交換法）。
先頭から最小値が並んでいく＝選択ソート（基本選択法）。
整列済みの手札に要素を挿入して右へずらす＝挿入ソート（基本挿入法）。
計算量はすべて最悪 O(n^2)。ほぼ整列済みで速いのは挿入ソート。

出典と仕様を確認する

IPA：FEシラバス Ver.9.2

IPA：試験で使用する用語・プログラム言語 Ver.5.1

Princeton：基本整列アルゴリズム