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

正解

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

正答率 55.3%（942人中 521人が正解）

問題の解説

ヒープソートは、未整列のデータを二分木 (ヒープ) の形に組み、根にある最小値 (又は最大値) を取り出して整列済みの部分へ移す操作を繰り返す。取り出すたびに残りをヒープに作り直し、計算量は平均も最悪も である。他の選択肢は、シェルソート、クイックソート、バブルソートの説明である。

選択肢ごとの解説

• ア一定の間隔だけ離れた要素から成る部分列ごとに整列し、間隔を段階的に詰めて最後に間隔 1 で整列する。これはシェルソートの説明である。
• イ基準値より大きい区分と小さい区分に要素を振り分け、各区分で同じ処理を繰り返す。これはクイックソートの説明である。
• ウ隣り合う要素を比べ、順序が逆なら入れ替える操作を繰り返す。これはバブルソートの説明である。
• エ正しい。未整列の部分を順序木 (ヒープ) にして最小値を取り出し、整列済みの部分へ移す操作を繰り返すのがヒープソートである。