スポンサーリンク

問題の解答・解説ページ

このページは解説の閲覧モードです。
実力試しをしたい方は、下のボタンからクイズに挑戦してください!

この問題をクイズ形式で解く
問題 No.3253
要素数が $6$ 個の配列 $[38, 27, 43, 3, 9, 82]$ に対して、バブルソート(隣接する要素の大小比較と交換を繰り返すアルゴリズム)を用いて昇順に整列を行う。配列の先頭から末尾に向かって走査する手順を $1$ 回のパスとしたとき、第 $1$ パスが終了した時点における配列の状態として正しいものはどれか。なお、バブルソートは左から右へ比較を行い、より大きな値を右へ移動させるものとする。

【正解の解説】

$[27, 38, 3, 9, 43, 82]$

水中で泡(バブル)がポコポコと軽いものから順に水面へ上がっていくように、一番重い数値(ここでは82)がプカプカと右端へ流されていく様子をイメージしてください。38と27を比べると38の方が大きいので右へ移動し、次に38と43を比べると43の方が大きいのでその場に留まり、今度は43と3を比べると…という風に、まるでバトンのリレーのように隣同士で大小比べをしながら進みます。左から順にコツコツと比較と入れ替えを1周分(第1パス)だけやりきると、この配列のように一番大きな『82』が綺麗に一番右の特等席へと辿り着きます。

スポンサーリンク

【その他の選択肢の解説】

$[38, 27, 3, 9, 43, 82]$

これは最初の「38と27」という絶好の比較チャンスを見逃して、何も並び替えをせずにそのままスルーしてしまったときの誤った状態です。バブルソートはスタート地点の左端から1つずつ確実に隣の奴とケンカ(大小比較)させていくルールなので、最初の手順をサボってしまうと絶対にこの配列にはなりません。出題者は「初学者ならどうせ途中で計算を面倒くさがって最初の並びのままに違いない」という甘えた心理を狙ってこの引っかけ選択肢を作っています。

$[3, 9, 27, 38, 43, 82]$

これは1回目のパスが終わった時点ではなく、何周も何周も粘り強く比較と入れ替えを繰り返して、完全に昇順に並び替えが終わったゴール(最終状態)の姿です。バブルソートは非常に慎重な性格なので、1回のパス(1周目の旅)が終わっただけでは、まだ一番右の82が確定するだけで他の数字たちはまだバラバラのままさまよっています。全部きれいに整列しているこの選択肢は、ゴールの旗を勘違いしてフラゲしてしまったフライング状態だと言えます。

$[82, 43, 38, 27, 9, 3]$

これは「昇順(小さい順)」ではなく、むしろ「降順(大きい順)」に無理やり並び替えようとして失敗したときのひどい有様です。問題文をよく読むと「より大きな値を右へ移動させる」と親切に書いてあるため、一番大きな82は自然と一番右側に吹き飛ばされるはずですが、この選択肢ではなぜか一番左に鎮座しています。これは鏡文字を見ているようなもので、右へ送るというバブルソートの大前提ルールを完全に逆走してしまった勘違いを誘う罠の選択肢です。