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

正解

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

正答率 55.3%（941人中 520人が正解）

問題の解説

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

選択肢ごとの解説

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