令和5年度 秋期 高度試験 午前I 問3
あるデータ列を整列したら状態0から順に状態1, 2, ・・・, Nへと推移した。整列に使ったアルゴリズムはどれか。
図の説明テキスト
データ列の整列アルゴリズムによる各状態の推移を示すリスト。状態 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回のパス（走査）が完了するごとに、未整列部分の最大値（または最小値）が端に確定していくという特徴があります。データの推移において、端から順に要素が確定していく様子から判定できます。
各選択肢の解説
- ア（クイックソート）: 適当な基準値（ピボット）を選び、それより小さいグループと大きいグループに分割する操作を再帰的に繰り返すアルゴリズムです。
- イ（挿入ソート）: 未整列のデータから1つを取り出し、整列済みのデータ列の適切な位置に挿入していくアルゴリズムです。
- ウ（バブルソート）: 正解です。隣接する要素を比較・交換し、端から順に要素を確定させます。
- エ（ヒープソート）: データを未整列のヒープ（木構造）に構成し、そこから最大値（または最小値）を取り出して整列済みデータに移す操作を繰り返すアルゴリズムです。