令和5年度 秋期 応用情報技術者試験 午前 問6
テクノロジ／アルゴリズムあるデータ列を整列したら状態 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年度 秋期 応用情報技術者試験 午前 問6
- アクイックソート
- イ挿入ソート
- ウバブルソート
- エヒープソート
正解：ウ
解説
状態1では最大値の9が末尾に確定し，状態2では次に大きい6が末尾から2番目に確定しています。このように「1回のパスごとに隣接要素の比較・交換を繰り返して最大値が末尾に沈んでいく」動きはバブルソートの特徴です。
選択肢ごとの解説
- ア誤り。クイックソートは基準値（ピボット）を境にデータを大小2つのグループへ分割していくため，パスごとに最大値が末尾に確定する動きにはなりません。
- イ誤り。挿入ソートは先頭側の整列済み部分が1要素ずつ広がっていく動きになります。状態1で末尾に9が移動する動きとは合いません。
- ウ正しい。隣接交換を繰り返し，パスごとに未確定部分の最大値が末尾に確定していくのはバブルソートです。
- エ誤り。ヒープソートはヒープ構造の構築と根の取り出しを繰り返すため，途中状態はヒープの配列表現となり，この推移とは異なります。