令和5年度 高度共通 午前I（PM試験） 問3

正解：ウ

AI解説

状態の推移を見ると、1回の走査（パス）ごとに最大値（又は最小値）が1つずつ端に確定していく。これは隣接する要素の比較・交換を繰り返して値を端へ『浮き上がらせる』バブルソートの特徴であり、ウが正解。判断基準は『パスごとに端から1要素ずつ整列済み領域が増えるか』である。 ア: クイックソートは基準値（ピボット）より小さい群と大きい群に分割することを再帰的に繰り返す。状態遷移は分割による群の並び替えとなり、端から1つずつ確定する形にはならない。 イ: 挿入ソートは先頭側の整列済み部分列に未整列要素を1つずつ挿入する。整列済み領域は増えるが、その中身は最終位置とは限らず、最大値が端に確定していく形にはならない。 ウ: 正解。隣接交換によりパスごとに最大（最小）値が端に確定するのはバブルソートの動きである。 エ: ヒープソートはヒープ（半順序木）を構成し、根の最大値を取り出して末尾と交換する。確定の仕方は似るが、途中状態はヒープ再構成による特有の並びになる。 💡 整列過程の識別は、クイック=ピボットで2分割、バブル=端から1つずつ確定、挿入=先頭側が常に整列済み（ただし値は未確定）、ヒープ=木構造の再構成、という途中状態の特徴で見分ける。