平成23年度 秋期 午前 問6

✓ これが正解エ未整列の部分を順序木にし，そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して，未整列の部分を縮めていく。

解説

未整列の部分を順序木にするのが目印です。

四つの記述はいずれも有名な整列の手順を述べたもので、そのうちヒープソートを述べているのはどれかを選ぶ設問です。ですから、何を道具にしている手順かで仕分けると迷いません。ヒープソートが使う道具は順序木です。手順は三段を行き来します。まず、まだ並んでいない部分を順序木の形に組みます。この木は、親が子より小さいという関係がすべての親子で保たれている形をしています。次に、その関係のおかげで根に来ている最小値を取り出し、並び終わった側の末尾へ移します。最後に残りをもう一度木の形へ整えて、初めに戻ります。これを繰り返すと未整列の部分が一つずつ縮み、やがて全体が並びます。見分けの手がかりは、木を組むと書いてあるかどうかの一点です。ほかの手順は、取り出す間隔や、振り分ける基準や、隣り合う相手といった別の道具を使っており、木はどこにも出てきません。ヒープソートの取り柄は、最悪の場合でも手間が崩れにくいことです。木の高さは要素数の対数に比例し、取り出す回数は要素数に等しいので、入力の並び方によらずほぼ一定の手間に収まります。

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

• アある間隔おきに取り出した要素から成る部分…：一定の間隔で飛び飛びに取り出した部分列をそれぞれ並べ、間隔を詰めながら同じ操作を繰り返す手順です。道具になっているのは取り出す間隔であって、親子の関係をもつ木ではありません。
• イ中間的な基準値を決めて，それよりも大きな…：中間的な基準となる値を決め、それより大きい側と小さい側に振り分けてから、区分ごとに同じ処理を繰り返す手順です。道具は振り分けの基準で、根から最小値を取り出す段はどこにもありません。
• ウ隣り合う要素を比較して，大小の順が逆であ…：隣り合う要素どうしを比べ、大小の順が逆であれば入れ替えるという操作を繰り返す手順です。比べる相手が常に隣に限られており、全体を木として組み直す考え方とは道具が違います。