応用情報技術者試験 応用情報技術者試験 平成28年度秋期 午前 問6: ヒープソートの説明として，適切なものはどれか。

問題本文

ヒープソートの説明として，適切なものはどれか。

選択肢

• ア.ある間隔おきに取り出した要素から成る部分列をそれぞれ整列し，更に間隔を詰めて同様の操作を行い，間隔が 1 になるまでこれを繰り返す。
• イ.中間的な基準値を決めて，それよりも大きな値を集めた区分と，小さな値を集めた区分に要素を振り分ける。次に，それぞれの区分の中で同様の処理を繰り返す。
• ウ.隣り合う要素を比較して，大小の順が逆であれば，それらの要素を入れ替えるという操作を繰り返す。
• エ.未整列の部分を順序木にし，そこから最小値を取り出して整列済みの部分に移す。この操作を繰り返して，未整列の部分を縮めていく。

正解

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

解説

代表的な整列アルゴリズムの手順を識別する問題。ヒープソートは、未整列データを「親が子より常に大きい(または小さい)」という制約をもつ完全2分木=ヒープ(順序木)に構成し、根に来る最小値(または最大値)を取り出して整列済み部分へ移し、残りで木を再構成する操作を繰り返すアルゴリズムである。木の根が必ず最小(最大)になるため線形探索せずに最小値を取り出せる点が高速さの理由で、計算量は O(n log n)。この「順序木にして根から取り出す」という記述に合致するエが正しい。

選択肢ごとの解説

• ア.一定間隔の要素群を整列し間隔を詰めていき最後に間隔1にする、という記述はシェルソートの説明であり、ヒープソートではない。
• イ.基準値(ピボット)を決めて大きい区分と小さい区分に振り分け、各区分で同じ処理を繰り返すのはクイックソートの説明である。
• ウ.隣り合う要素を比較し逆順なら交換する操作の繰り返しはバブルソート(隣接交換法)の説明であり、ヒープソートではない。
• エ.未整列部分を順序木(ヒープ)にし、根から最小値を取り出して整列済み部分へ移す操作を繰り返すという記述はヒープソートそのものであり、正しい。