応用情報技術者平成28年秋期午前6

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

１、ヒープソートは、
未整列データを「親の値≦子の値」(または「親の値≧子の値」)の関係をもつ順序木として表現し、整列後の根の値(最小値または最大値)を取り出すことを繰り返して整列を行う方法です。

ヒープとはtreeであって、なおかつheap propertyを満たす物のことです。
heap propertyとは、全てのノードは子のノードよりも小さいというものです。
特に今回は標語的に「上は小、下は大」という感じで読み進めてください。

これがヒープの例

必然的に根が最小値になります。

２、
・ある間隔おきに取り出した要素から成る部分列をそれぞれ整列し，更に間隔を詰めて同様の操作を行い，間隔が1になるまでこれを繰り返す。
⇒シェルソートの説明です。

・中間的な基準値を決めて，それよりも大きな値を集めた区分と，小さな値を集めた区分に要素を振り分ける。次に，それぞれの区分の中で同様な処理を繰り返す。
⇒クイックソートの説明です。

・隣り合う要素を比較して，大小の順が逆であれば，それらの要素を入れ替えるという操作を繰り返す。
⇒バブルソートの説明です。