応用情報技術者 2016年 秋期 午前2 問06
問題文
ヒープソートの説明として、適切なものはどれか。
選択肢
ア：ある間隔おきに取り出した要素から成る部分列をそれぞれ整列し、更に間隔を詰めて同様の操作を行い、 間隔が1になるまでこれを繰り返す。
イ：中間的な基準値を決めて、 それよりも大きな値を集めた区分と、 小さな値を集めた区分に要素を振り分ける。 次に、 それぞれの区分の中で同様な処理を繰り返す。
ウ：隣り合う要素を比較して、 大小の順が逆であれば、それらの要素を入れ替えるという操作を繰り返す。
エ：未整列の部分を順序木にし、そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して、 未整列の部分を縮めていく。（正解）
ヒープソートの説明 +【午前2 解説】
要点まとめ
- 結論：ヒープソートは未整列部分をヒープ（順序木）に変換し、最小値または最大値を取り出して整列済みに移す手法です。
- 根拠：ヒープ構造は完全二分木で、親ノードが子ノードより大きい（または小さい）という性質を持ち、効率的に最大値・最小値を取得可能です。
- 差がつくポイント：ヒープソートは「ヒープ構造の構築」と「ヒープからの要素取り出し」を繰り返す点で、他のソート（シェルソート、クイックソート、バブルソート）と明確に異なります。
正解の理由
選択肢エは「未整列の部分を順序木（ヒープ）にし、そこから最小値を取り出して整列済の部分に移す」というヒープソートの基本的な流れを正確に説明しています。ヒープソートはヒープ構造を利用して最大値または最小値を効率的に取り出し、整列済み領域を拡大していくアルゴリズムです。
よくある誤解
- ヒープソートは「隣接要素の比較と交換を繰り返す」バブルソートとは異なります。
- 「間隔を詰めて部分列を整列する」シェルソートと混同しやすい点に注意が必要です。
解法ステップ
- 配列全体をヒープ（最大ヒープまたは最小ヒープ）に構築する。
- ヒープの根（最大値または最小値）を取り出し、整列済み領域に移す。
- ヒープのサイズを縮小し、ヒープ条件を維持するために再調整（ヒープ化）を行う。
- 2〜3の操作を繰り返し、全要素を整列済みに移すまで続ける。
選択肢別の誤答解説
- ア：間隔を詰めて部分列を整列するのはシェルソートの説明であり、ヒープソートとは異なります。
- イ：基準値で区分けし再帰的に処理するのはクイックソートの特徴です。
- ウ：隣接要素の比較と交換を繰り返すのはバブルソートの説明で、ヒープソートではありません。
- エ：ヒープ構造を利用し、未整列部分から最小値を取り出す操作を繰り返す正しい説明です。
補足コラム
ヒープソートは安定ソートではありませんが、時間計算量は常にであり、最悪ケースでも効率的に動作します。メモリ使用量ものため、メモリ制約が厳しい環境でも有用です。ヒープ構造の理解は優先度付きキューなど他のアルゴリズムにも役立ちます。
FAQ
Q: ヒープソートは安定なソートですか？
A: いいえ、ヒープソートは安定ソートではありません。要素の順序が変わる可能性があります。
A: いいえ、ヒープソートは安定ソートではありません。要素の順序が変わる可能性があります。
Q: ヒープソートの時間計算量は？
A: ヒープソートの時間計算量は平均・最悪ともにです。
A: ヒープソートの時間計算量は平均・最悪ともにです。
Q: ヒープとは何ですか？
A: ヒープは完全二分木で、親ノードが子ノードより大きい（最大ヒープ）または小さい（最小ヒープ）という性質を持つデータ構造です。
A: ヒープは完全二分木で、親ノードが子ノードより大きい（最大ヒープ）または小さい（最小ヒープ）という性質を持つデータ構造です。
関連キーワード: ヒープソート、ヒープ構造、ソートアルゴリズム、最大ヒープ、最小ヒープ、時間計算量
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！