令和3年度 秋期 午前 問5

✓ これが正解ウ隣り合う要素を比較して，大小の順が逆であれば，それらの要素を入れ替えるという操作を繰り返す。

解説

隣り合う要素の大小を比べて入れ替える方法です。

設問は、四通りの整列アルゴリズムの説明の中からバブルソートに当たるものを選ばせています。ですから見分けの軸は、比較する相手が隣どうしに限られるか、それとも間を空けた要素、または基準値、あるいは木の構造から取り出した要素かという、比較の相手の位置についての一点だけです。この方法は、列の先頭から末尾に向かって、隣り合う二つを取り出しては大小の順が逆であれば入れ替えるという単純な操作を繰り返し、一巡するごとに一番大きい値が端まで持ち上がっていく流れをたどります。名前が示すとおり、値の泡が浮き上がっていく様子に見立てられていて、比較の相手がつねに隣どうしに限られる点が、他の整列アルゴリズムから見分ける決め手になります。

ほかの選択肢はなぜ違うのか

• アある間隔おきに取り出した要素から成る部分…：ある間隔ごとに要素を取り出して部分列を作り、間隔を詰めながら同じ操作を繰り返す方法の説明です。比較の相手が隣り合う要素ではなく間を空けて取り出した要素になっており、この設問が問う手順とは動きが違います。
• イ中間的な基準値を決めて，それよりも大きな…：中間的な基準値を決めて大きい側と小さい側に振り分け、それぞれを再び同じ操作で分けていく方法の説明です。比較の相手は隣どうしではなく基準値で、動きの単位が振り分けになっています。
• エ未整列の部分を順序木にし，そこから最小値…：未整列の部分を順序木にして最小値を取り出し、整列済みの部分に移していく方法の説明です。木の構造から取り出す仕組みで、隣接した要素どうしの入れ替えは行っていません。