応用情報技術者 2013年 秋期 午前2 問09
問題文
未整列の配列 ()を、流れ図で示すアルゴリズムによって昇順に整列する。での値がそれぞれ、21, 5, 53, 71, 3, 17の場合、流れ図において、との値の入替えは何回行われるか。
選択肢
ア：3
イ：6
ウ：8（正解）
エ：15
未整列配列の昇順整列における入替え回数の計算【午前2 解説】
要点まとめ
- 結論：与えられた流れ図はバブルソートであり、入替え回数は8回となる。
- 根拠：配列の隣接要素を比較し、大小関係が逆なら交換を繰り返すため、実際に手順を追うことで入替え回数が算出できる。
- 差がつくポイント：流れ図のループ範囲と比較条件を正確に理解し、手計算で交換回数を丁寧に数えることが重要。
正解の理由
この流れ図はバブルソートの典型的なアルゴリズムを示しています。配列の隣接要素を比較し、左の要素が右の要素より大きければ交換します。与えられた配列 [21, 5, 53, 71, 3, 17] に対して、ループを回しながら交換回数を数えると合計8回の入替えが発生します。したがって、正解はウ: 8です。
よくある誤解
隣接要素の比較範囲やループの増分・終値を誤解し、交換回数を過小評価または過大評価することがあります。特に内側ループの範囲設定を間違えると正しい回数が出ません。
解法ステップ
- 配列の初期状態を確認する： [21, 5, 53, 71, 3, 17]
- 外側ループ i を 1 から n-1 (5) まで回す。
- 内側ループ j を n (6) から i+1 まで逆方向に回す。
- 各 j で a[j-1] と a[j] を比較し、a[j-1] > a[j] なら交換し、交換回数をカウント。
- 全ループ終了まで繰り返し、合計交換回数を求める。
- 手計算で各ステップの交換を丁寧に追い、合計8回と判定する。
選択肢別の誤答解説
- ア: 3
交換回数を少なく見積もりすぎ。バブルソートの特性上、もっと多くの交換が必要。 - イ: 6
途中の交換を見落としている可能性が高い。内側ループの範囲を誤解している。 - ウ: 8
正解。正確に手順を追い、交換回数を正しく数えた結果。 - エ: 15
交換回数を多く見積もりすぎ。バブルソートの最大交換回数は だが、実際は8回。
補足コラム
バブルソートは隣接要素を比較し、大小関係が逆なら交換を繰り返す単純な整列アルゴリズムです。最悪計算量は ですが、実装が簡単で教育用に適しています。今回の問題の流れ図は典型的なバブルソートの構造を示しており、内側ループが逆方向に動く点が特徴です。
FAQ
Q: なぜ内側ループは逆方向に動くのですか？
A: バブルソートでは大きい値が右端に「泡のように」浮かび上がるため、内側ループは後ろから前に向かって比較・交換を行います。
A: バブルソートでは大きい値が右端に「泡のように」浮かび上がるため、内側ループは後ろから前に向かって比較・交換を行います。
Q: 交換回数は配列の初期状態によってどう変わりますか？
A: 配列がほぼ整列済みなら交換回数は少なく、逆順に近いほど多くなります。最大は 回です。
A: 配列がほぼ整列済みなら交換回数は少なく、逆順に近いほど多くなります。最大は 回です。
関連キーワード: バブルソート、配列整列、アルゴリズム、交換回数、流れ図解析
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！