令和5年度 秋期 応用情報技術者試験 午前 問6
あるデータ列を整列したら状態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つずつ取り出し、整列済みのデータ列の適切な位置に挿入していくアルゴリズムです。
- ウ バブルソート: 隣り合う要素を比較し、大小関係が逆であれば交換する処理を繰り返すことで整列を行います。（正解）
- エ ヒープソート: 未整列のデータからヒープ（順序木・完全二分木）を作成し、ルートノード（最大値または最小値）を取り出して整列済みとする操作を繰り返します。