CO-S33｜情報Ⅰ 対策問題

正答

1

この問題のポイント

バブルソート1パスのトレース を問う問題です。隣どうしの比較・交換を1手ずつ書き出せるかがカギです。

解説

バブルソートは、隣どうしの2つを比較して、順序が逆(昇順なら左が大きい)なら交換する、という操作を先頭から末尾まで繰り返す整列アルゴリズムです。泡(バブル)が水面に浮かぶように、大きい値が右端へ移動していくのが名前の由来です。この問題は「1回目の走査(1パス)が終わった直後」の状態を問うています。

[5, 3, 8, 1] に対して、隣どうしの比較を1手ずつ追います。

1. 1組目(5, 3): 5 > 3 で逆順 → 交換 → [3, 5, 8, 1]
2. 2組目(5, 8): 5 < 8 で正しい順 → そのまま → [3, 5, 8, 1]
3. 3組目(8, 1): 8 > 1 で逆順 → 交換 → [3, 5, 1, 8]

よって1パス後は [3, 5, 1, 8] です。注目すべきは、最大値の8が末尾に確定したこと。バブルソートは1パスごとに「残りの中の最大値が1つ右端に確定」していき、パスを繰り返すと全体が整列します(2パス目で[3, 1, 5, 8]、3パス目で[1, 3, 5, 8])。

共通テストでは「途中経過の配列を選ぶ」形が定番で、完全に整列した最終形 [1, 3, 5, 8] がひっかけとして必ず並びます。問われているのが「1回目の走査の直後」であることを確認し、1手ずつ配列を書き出して答えましょう。

選択肢の確認

1．○ 交換→そのまま→交換をたどった正しい1パス後の状態。
2．× [1, 3, 5, 8]は全パス終了後の完全に整列した状態。1パスでは届かない。
3．× [5, 3, 8, 1]は交換を1度も行っていない初期状態のまま。
4．× [3, 5, 8, 1]は最後の組(8, 1)の交換が抜けている。

ここだけは覚えよう

バブルソートは1パスで最大値が右端に確定 — 途中経過は「比較→交換」を1手ずつ書き出す。