応用情報技術者 2023年 秋期 午前2 問06
問題文
あるデータ列を整列したら状態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
選択肢
ア：クイックソート
イ：挿入ソート
ウ：バブルソート（正解）
エ：ヒープソート
あるデータ列の整列過程から推測するアルゴリズム【午前2 解説】
要点まとめ
- 結論：与えられた状態遷移は隣接要素の交換を繰り返すバブルソートの特徴を示しています。
- 根拠：状態1で最大値9が末尾に移動し、以降も隣接要素の交換で徐々に整列が進んでいる点がバブルソートの典型的な動作です。
- 差がつくポイント：他のソートは部分的な並び替えやピボット選択など異なる動作をするため、状態遷移の様子から正確に判別できることが重要です。
正解の理由
バブルソートは隣接する要素を比較し、大小関係が逆なら交換していくことで最大値が右端に「泡のように」浮かび上がる動きをします。問題の状態0から状態1への変化で、最大値9が末尾に移動していることが明確に示されており、これがバブルソートの典型的な特徴です。以降の状態遷移も隣接交換を繰り返しているため、ウ: バブルソートが正解です。
よくある誤解
クイックソートやヒープソートは部分的に大きな要素を移動させますが、隣接要素の交換を繰り返す動作はしません。挿入ソートは部分的に整列済みの領域を拡大しますが、最大値が末尾に移動する動きは異なります。
解法ステップ
- 状態0と状態1の変化を確認し、どの要素がどの位置に移動したかを把握する。
- 最大値9が隣接交換で末尾に移動していることを確認する。
- 以降の状態遷移も隣接要素の交換で整列が進んでいるかを検証する。
- 各ソートアルゴリズムの特徴と照らし合わせ、隣接交換を繰り返すバブルソートと判断する。
選択肢別の誤答解説
- ア: クイックソート
ピボットを基準に分割し部分配列を再帰的に整列するため、隣接交換の連続的な動きは見られません。 - イ: 挿入ソート
整列済み部分に新しい要素を挿入する形で進むため、最大値が末尾に移動する動きは異なります。 - ウ: バブルソート
隣接要素を比較・交換し、最大値が末尾に移動する動きが問題の状態遷移と一致します。 - エ: ヒープソート
ヒープ構造を利用し最大値を取り出すため、隣接交換の連続的な動きはありません。
補足コラム
バブルソートは最も基本的なソートアルゴリズムの一つで、隣接要素の交換を繰り返すため動作が視覚的に理解しやすい特徴があります。一方で計算量はと効率は良くありません。実務ではより高速なクイックソートやヒープソートが多用されますが、アルゴリズムの基礎理解には重要です。
FAQ
Q: バブルソートはなぜ最大値が末尾に移動するのですか？
A: 隣接要素を比較し大きい方を右に交換するため、最大値が右端に「泡のように」浮かび上がる動きになるからです。
A: 隣接要素を比較し大きい方を右に交換するため、最大値が右端に「泡のように」浮かび上がる動きになるからです。
Q: 挿入ソートとバブルソートの見分け方は？
A: 挿入ソートは整列済み部分に新しい要素を挿入する形で進み、隣接交換の連続的な最大値移動は起こりません。
A: 挿入ソートは整列済み部分に新しい要素を挿入する形で進み、隣接交換の連続的な最大値移動は起こりません。
関連キーワード: バブルソート、ソートアルゴリズム、隣接交換、整列過程、アルゴリズム特徴
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！