基本情報技術者 一問一答｜B 第195問

解説

バブルソートの1パス目は、隣接する要素を先頭から順に比較し、左が大きければ交換する。{5,2,8,1,9}に対して、①5と2を比較→5>2で交換し{2,5,8,1,9}、②5と8を比較→5≦8で交換なし、③8と1を比較→8>1で交換し{2,5,1,8,9}、④8と9を比較→8≦9で交換なし。よって1パス目終了時は{2,5,1,8,9}で正解である。{1,2,5,8,9}は全パス完了後の最終結果であり、1パスだけでは到達しない。{5,2,8,1,9}は交換が行われなかったとする誤り、{2,5,8,1,9}は②の比較までで止めた途中状態である。頻出ポイントは「1パス終了時に最大値が必ず末尾に確定する」という性質であり、nパス目までに右からn個が確定することを押さえるとパス数を問う問題にも対応できる。