応用情報技術者試験 応用情報技術者試験 令和5年度秋期 午前 問6: あるデータ列を整列したら状態 0 から順に状態 1，2，・・・，N へと推移した。整列に使ったアルゴリズムはどれか。 状態 0 3，5，9，6，1，2 状態 1

正解

ウ. バブルソート

正答率 42.1%（1,485人中 625人が正解）

問題の解説

整列の途中経過から，どのアルゴリズムかを見抜く問題です。バブルソートは隣り合う要素を比較・交換しながら1周ごとに最大値を末尾へ送り込むのが特徴で，周回のたびに末尾から順に最大値が確定していきます。状態0→1で最大値9が末尾に移動し，状態1→2では次に大きい6が後方(末尾の手前側)へ確定していく動きが見られるため，これはバブルソートの挙動です。よって正解はウです。

選択肢ごとの解説

• アクイックソートは基準値で大小2グループに分割していくため，各段階で配列が基準値の左右に振り分けられる動きになり，末尾から1つずつ最大値が確定するこの過程とは異なります。
• イ挿入ソートは先頭から順に，整列済みの左側部分へ各要素を割り込ませるため，左側から整っていく動きになり，末尾の大きい値から確定していくこの過程とは異なります。
• ウ正しい。隣接要素を比較・交換し，1周ごとに最大値が末尾に確定していくバブルソートの動きと一致します。
• エヒープソートはヒープ木を構成してから根(最大値)を末尾に置く操作を繰り返すため，途中経過で木の再構成に伴う離れた要素の入れ替えが生じ，この単純な隣接交換の過程とは異なります。