平成25年度 春期 応用情報技術者試験 午前 問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
出典：平成25年度 春期 応用情報技術者試験 午前 問6
- アクイックソート
- イ挿入ソート
- ウバブルソート
- エヒープソート
正解：ウ
解説
状態0から状態1では末尾の9が確定し，状態1から状態2では末尾から2番目の6が確定しています。このように1回の走査ごとに隣接要素を比較・交換して最大値を末尾側に沈めていく動きはバブルソートの特徴です。
選択肢ごとの解説
- ア誤り。クイックソートは基準値で分割統治的に整列するため，このように末尾から1要素ずつ確定していく推移にはなりません。
- イ誤り。挿入ソートは整列済み部分を先頭側から徐々に広げていく方式であり，末尾側から値が確定していく本問の推移とは異なります。
- ウ正しい。隣接要素の比較・交換を繰り返すバブルソートでは，1回の走査で最大の未確定値が末尾に確定していきます。
- エ誤り。ヒープソートはヒープ構造を使って整列するため，本問のように単純な隣接交換の推移にはなりません。