応用情報技術者 2021年 秋期 午前2 問05
問題文
バブルソートの説明として、適切なものはどれか。
選択肢
ア：ある間隔おきに取り出した要素から成る部分列をそれぞれ整列し、更に間隔を詰めて同様の操作を行い、間隔が1になるまでこれを繰り返す。
イ：中間的な基準値を決めて、それよりも大きな値を集めた区分と、小さな値を集めた区分に要素を振り分ける。次に、それぞれの区分の中で同様の操作を繰り返す。
ウ：隣り合う要素を比較して、大小の順が逆であれば、それらの要素を入れ替えるという操作を繰り返す。（正解）
エ：未整列の部分を順序木にし、そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して、未整列の部分を縮めていく。
バブルソートの説明 +【午前2 解説】
要点まとめ
- 結論：バブルソートは隣接する要素を比較し、大小が逆なら交換を繰り返す単純な整列アルゴリズムです。
- 根拠：隣り合う要素の交換を繰り返すことで、最大値が徐々に末尾に「泡のように」浮かび上がる動作が特徴です。
- 差がつくポイント：他の選択肢はシェルソート、クイックソート、ヒープソートの説明であり、バブルソートの基本動作を正確に理解することが重要です。
正解の理由
選択肢ウは「隣り合う要素を比較し、大小の順が逆なら入れ替える操作を繰り返す」とあり、これはバブルソートの典型的な動作を正しく表しています。バブルソートは単純で理解しやすい反面、効率は良くありませんが、問題文の説明としては最も適切です。
よくある誤解
バブルソートは単に「並べ替え」ではなく、隣接要素の比較と交換を繰り返すことが特徴です。間隔を空けて比較するのはシェルソートの特徴であり、混同しやすい点です。
解法ステップ
- 問題文の説明を読み、バブルソートの特徴を思い出す。
- 選択肢の説明をそれぞれの代表的なソートアルゴリズムと照合する。
- 隣接要素の比較と交換を繰り返す説明がある選択肢を選ぶ。
- 他の選択肢はシェルソート（ア）、クイックソート（イ）、ヒープソート（エ）であることを確認。
- 正解はウと判断する。
選択肢別の誤答解説
- ア: ある間隔おきに要素を整列し間隔を詰める操作はシェルソートの説明であり、バブルソートではない。
- イ: 基準値で区分けし再帰的に整列するのはクイックソートの特徴で、バブルソートとは異なる。
- ウ: 隣接要素を比較し交換を繰り返す動作はバブルソートの基本で正解。
- エ: 順序木（ヒープ）から最小値を取り出す操作はヒープソートの説明であり、バブルソートではない。
補足コラム
バブルソートは教育用やアルゴリズム入門でよく使われますが、計算量はと非効率です。実務ではクイックソートやマージソートなど高速なアルゴリズムが多用されます。シェルソートはバブルソートの改良版とも言え、間隔を空けて比較することで高速化を図っています。
FAQ
Q: バブルソートはどんな場合に使われますか？
A: 教育目的や小規模データの整列に使われますが、大規模データには不向きです。
A: 教育目的や小規模データの整列に使われますが、大規模データには不向きです。
Q: バブルソートの計算量は？
A: 最悪・平均ともにで、効率は良くありません。
A: 最悪・平均ともにで、効率は良くありません。
Q: シェルソートとバブルソートの違いは？
A: シェルソートは間隔を空けて比較・交換し、段階的に整列を進める点が異なります。
A: シェルソートは間隔を空けて比較・交換し、段階的に整列を進める点が異なります。
関連キーワード: バブルソート、ソートアルゴリズム、隣接交換、シェルソート、クイックソート、ヒープソート
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！