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

問題本文

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

選択肢

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

正解

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

解説

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

選択肢ごとの解説

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