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

選択肢

• ア.クイックソート
• イ.挿入ソート
• ウ.バブルソート
• エ.ヒープソート

正解

ウ. バブルソート

解説

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

選択肢ごとの解説

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