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

アルゴリズム問題の中で、探索（二分探索）と並んで毎年必ず出題される王道テーマが「整列（ソート：Sorting）アルゴリズム」です。

特に基本となる「バブルソート（基本交換法）」「選択ソート（基本選択法）」「挿入ソート（基本挿入法）」の3つは、コードの穴埋めやループ実行後の配列状態を問う問題が頻出します。

本記事では、3大基本ソートの動作メカニズムを図解で比較し、「整列済領域と未整列領域の境界」「各パス終了時の配列の並び」を手元で正確にトレースする実践テクニックを徹底解説します。

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

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

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

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

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

【トレースの鉄則】：バブルソートは外側ループが 1 回回るごとに、「一番右端（末尾）に未整列領域の最大値が 1 つずつ確定」していきます。問題で「第2パス終了時の配列はどれか」と問われたら、右端2つが昇順最大になっている選択肢を絞り込みましょう。

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

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

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

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

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

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

○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` とすることで、隙間に新しい値が正しく収まります。

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

1. 末尾から最大値が固まっていく ＝ バブルソート（基本交換法）。

2. 先頭から最小値が並んでいく ＝ 選択ソート（基本選択法）。

3. 整列済みの手札に要素を挿入して右へずらす ＝ 挿入ソート（基本挿入法）。

4. 計算量はすべて最悪 $O(n^2)$。ほぼ整列済みで速いのは挿入ソート。