応用情報技術者 2022年 秋期 午前2 問06

バブルソートの処理【午前2解説】

正解の理由

解法ステップ

1. ループの添字を読み取る：外側が i：1 → n−1、内側が j：n → i+1（減少）であることを確認する。
2. 判定ノードの比較対象が A[j] と A[j−1] の隣接要素比較であると認識する。
3. 比較の結果が「＜」ならば三行の代入で A[j] と A[j−1] を交換していることを確認する。
4. 「隣接要素の比較＋条件付き交換」を内側ループで繰り返すアルゴリズム群（バブル系）に該当すると判断する。
5. 選択肢を照合して、交換が隣接要素同士で逐次行われる点からバブルソート（エ）と結論づける。

選択肢別の誤答解説

• ア: クイックソート
  クイックソートはピボットによる分割（partition）と再帰を用いる。図に再帰やピボット選択、範囲分割の処理が見られないため該当しない。
• イ: 選択ソート
  選択ソートは各外側反復で範囲内の最小（または最大）を探して一度だけ位置を交換する（最小値の位置を記録して外側ループの末尾で入れ替える）。図は隣接交換を繰り返して移動させているため「一度だけの交換」という挙動と合致しない。
• ウ: 挿入ソート
  挿入ソートは現在の要素（キー）を取り出して左側の整列済み部分をシフトして挿入する方式で、通常は一時変数 key を使ってループ内で要素を右へ移動させる。図では key を使したシフトではなく、隣接要素の交換（3行の代入）を行っており実装パターンが異なる。
• エ: バブルソート（正解）
  隣接比較と条件付き交換を内側ループで行い、外側ループで範囲を狭めていく構造はバブルソートの典型的な変形であるため一致する。

よくある誤解

1. 「A[j] ≥ A[j−1] の時に内側ループを直ちに抜ける」と誤解するケース
   • 実際には ≧ の矢印はループ2の制御に戻るもので、そこで j が次の値へ進み（減少し）内側ループの次反復へ入る動作です。即時の内側ループ抜け（外側ループへの遷移）を意味しません。
2. 交換がひとつの j で何度も起きて要素が一気に左へ移動すると考える誤り
   • 図の流れでは、交換後に判定ノードへ戻り通常は ≧ 分岐に入って次の j に進みます。つまり一度の j 反復で行われる交換は基本的に一回で、要素が複数位置移動するのは次の j 値で再び交換が行われることによる連続的な効果です。

補足コラム

• 挙動のイメージ：このフローチャートは「右端から左へ向かって隣接要素を比較し、条件に応じて交換する」パターンです。外側ループ i が進むごとに左側に最小値がひとつずつ確定していきます（最小要素が左へ“泡のように”移動）。
• 計算量は典型的に平均・最悪ともに $O(n^2)$、安定なソートであり、追加領域は $O(1)$（インプレース）です。
• フローチャートに対応する 0-based Python 実装例（図の動作に一致）:

def bubble_variant(A):
    n = len(A)
    for i in range(0, n-1):            # i = 0 .. n-2  (図の i=1..n-1 に対応)
        for j in range(n-1, i, -1):    # j = n-1 .. i+1
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j-1], A[j]

FAQ