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

正解

ウ. バブルソート

正答率 42.1%（1,488人中 626人が正解）

問題の解説

状態が進むごとに、最大の値が末尾へ移っていく。状態 0 から 1 では 9 が 6、1、2 と順に入れ替わって末尾に移り、状態 1 から 2 では 6 が 1、2 と入れ替わって 9 の手前に移る。隣り合う要素を比べて入れ替えながら、大きい値を後ろへ運ぶこの動きは、バブルソートである。

選択肢ごとの解説

• ア基準値（ピボット）を選んで、小さい値の組と大きい値の組に分けながら進む方法である。最大値だけが末尾へ移る状態 1 のような変化にはならない。
• イ整列済みの部分に、未整列の要素を一つずつ正しい位置へ挿入していく方法である。状態 0 の 3, 5, 9 は整列済みで、次は 6 が 9 の手前に入るため、状態 1 とは異なる。
• ウ正しい。隣り合う要素を比べて入れ替えながら端まで進む操作を繰り返し、一回の走査ごとに最大値が末尾に確定していく。
• エ最大値を根から取り出して末尾と交換し、残りをヒープに作り直す方法である。交換のたびに先頭側の並びが大きく変わるので、3, 5 が先頭に残る状態 1 にはならない。