整列アルゴリズムの推移

推移過程を観察します。 状態 0: [3, 5, 9, 6, 1, 2] 状態 1: [3, 5, 6, 1, 2, 9] → 最大値 9 が隣接交換により末尾に確定 状態 2: [3, 5, 1, 2, 6, 9] → 2番目に大きい 6 が末尾から2番目に確定 このように，隣接する要素同士を比較・交換しながら走査を繰り返し，各走査ごとに最大値（または最小値）が端へ浮かび上がる（あるいは沈む）ように整列していく手法は「バブルソート（基本交換法）」の特徴です。したがって正解はウとなります。 各選択肢の解説は以下のとおりです。 基準値（ピボット）を選び，それより小さい要素と大きい要素に分割して再帰的に整列します。 整列済みの列に対して，未整列の要素を適切な位置に挿入していく整列手法です。 データを二分ヒープ木構造に構成し，根から最大値を取り出して再構成を繰り返す整列手法です。 状態 データ列 変化 0 3, 5, 9, 6, 1, 2 1 3, 5, 6, 1, 2, 9 9 が隣と交換を繰り返して末尾へ 2 3, 5, 1, 2, 6 , 9 6 が末尾から2番目へ 1回の走査ごとに、未整列部分の最大値が隣どうしの交換で末尾側へ移動しています。これはバブルソートの動きです。

あるデータ列を整列したら状態0から順に状態1, 2, ..., Nへと推移した。整列に使ったアルゴリズムはどれか。

状態 0 : 3, 5, 9, 6, 1, 2
状態 1 : 3, 5, 6, 1, 2, 9
状態 2 : 3, 5, 1, 2, 6, 9
　　　　・
　　　　・
　　　　・
状態 N : 1, 2, 3, 5, 6, 9

出典令和5年度 秋期 高度情報処理技術者試験 午前Ⅰ 問3
ア
クイックソート
イ
挿入ソート
ウ
バブルソート
エ
ヒープソート