応用情報技術者 2024年 春期 午前2 問07
問題文
整列方法に関するアルゴリズムの記述のうち、バブルソートの記述はどれか。ここで、整列対象は重複のない1から9の数字がランダムに並んでいる数字列とする。
選択肢
ア：数字列の最後の数字から最初の数字に向かって、隣り合う二つの数字を比較して小さい数字が前に来るよう数字を入れ替える操作を繰り返し行う。（正解）
イ：数字列の中からランダムに基準となる数を選び、基準より小さい数と大きい数の二つのグループに分け、それぞれのグループ内も同じ操作を繰り返し行う。
ウ：数字列をほぼ同じ長さの二つの数字列のグループに分割していき、分割できなくなった時点から、グループ内で数字が小さい順に並べる操作を繰り返し行う。
エ：未処理の数字列の中から最小値を探索し、未処理の数字列の最初の数字と入れ替える操作を繰り返し行う。
整列方法に関するアルゴリズムの記述のうち、バブルソートの記述はどれか【午前2 解説】
要点まとめ
- 結論：バブルソートは隣接する数字を比較し、大小関係に応じて入れ替えを繰り返す単純な交換ソートである。
- 根拠：選択肢アは「隣り合う二つの数字を比較し、小さい数字が前に来るよう入れ替える」と正確にバブルソートの特徴を表している。
- 差がつくポイント：バブルソートは隣接要素の比較と交換を繰り返す点で、基準値で分割するクイックソートや分割統治法のマージソートとは明確に異なる。
正解の理由
選択肢アは「数字列の最後から最初に向かって隣り合う数字を比較し、小さい数字が前に来るよう入れ替える」と記述しており、これはバブルソートの典型的な動作を示しています。バブルソートは隣接要素を比較し、大小関係に応じて交換を繰り返すことで、最大値が徐々に末尾に「泡のように浮かび上がる」動きをします。これに対し、他の選択肢はクイックソート（イ）、マージソート（ウ）、選択ソート（エ）の説明であり、バブルソートの特徴とは異なります。
よくある誤解
バブルソートは単純な交換ソートであるため、隣接要素の比較と交換を繰り返す点が重要です。基準値で分割したり、最小値を探索して交換するのは別のアルゴリズムです。
解法ステップ
- 問題文で「バブルソート」を問われていることを確認する。
- バブルソートの特徴を思い出す：隣接要素の比較と交換を繰り返す。
- 各選択肢の説明を読み、隣接要素の比較と交換を行うものを探す。
- 選択肢アが隣接要素の比較と交換を正確に説明していることを確認。
- 他の選択肢はクイックソート、マージソート、選択ソートの説明であるため除外。
選択肢別の誤答解説
- ア: 正解。隣接要素を比較し、小さい数字が前に来るよう入れ替える動作はバブルソートの本質。
- イ: クイックソートの説明。基準値を選び、分割して再帰的に処理するためバブルソートではない。
- ウ: マージソートの説明。分割統治法で配列を分割し、マージしながら整列する。
- エ: 選択ソートの説明。未処理部分から最小値を探し、先頭と交換する方法でバブルソートとは異なる。
補足コラム
バブルソートは理解しやすいアルゴリズムですが、計算量はと非効率です。実務ではクイックソートやマージソートがよく使われますが、教育用やアルゴリズム学習の入門として重要な位置を占めています。
FAQ
Q: バブルソートはどのような場合に効率が良いですか？
A: ほぼ整列済みの配列に対しては、交換が少なくなるため効率が改善しますが、基本的にはの計算量です。
A: ほぼ整列済みの配列に対しては、交換が少なくなるため効率が改善しますが、基本的にはの計算量です。
Q: バブルソートと選択ソートの違いは何ですか？
A: バブルソートは隣接要素を比較し交換を繰り返すのに対し、選択ソートは未整列部分から最小値を探して先頭と交換します。
A: バブルソートは隣接要素を比較し交換を繰り返すのに対し、選択ソートは未整列部分から最小値を探して先頭と交換します。
関連キーワード: バブルソート、クイックソート、マージソート、選択ソート、アルゴリズム、ソート、整列、計算量
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！