情報処理安全確保支援士試験 情報セキュリティスペシャリスト試験 平成28年度秋期 午前Ⅰ 問3: ヒープソートの説明として，適切なものはどれか。

正解

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

問題の解説

ヒープソートの定義を問う基本問題。ヒープソートは未整列データを順序木（ヒープ）として構成し，根にある最小値（または最大値）を取り出して整列済み部分へ移し，残りを再びヒープ化する操作を繰り返す。よってエが該当。平均・最悪ともにO(n log n)で，追加メモリが少ない点が特徴。アはシェルソート，イはクイックソート，ウはバブルソートで，整列アルゴリズムの分類を整理しておきたい。

選択肢ごとの解説

• ア間隔をあけて部分列を整列し間隔を詰めていくのはシェルソートの説明で誤り。
• イ基準値で大小に振り分けて再帰するのはクイックソートであり誤り。
• ウ隣接要素の比較交換を繰り返すのはバブルソートで，ヒープソートではない。
• エ順序木から最小値を取り出して整列部分へ移す反復がヒープソートの本質で正しい。