平成28年度 秋期 応用情報技術者 問6

正解 エ

ヒープソートは、未整列の部分をヒープ（順序木）にして根から最小値（または最大値）を取り出す操作を繰り返す整列法です。

ヒープは、親の値が子の値以下（または以上）になるように保たれた完全2分木です。根には常に最小値（または最大値）が置かれます。ヒープソートでは、根の値を取り出して整列済の部分に移し、残りの要素でヒープを作り直します。この操作を繰り返すと未整列の部分が縮み、全体が整列されます。計算量は最悪でもO(n log n)です。

ア：シェルソートは、一定の間隔おきに取り出した要素の部分列を整列し、間隔を詰めながら繰り返す整列法です。

イ：クイックソートは、基準値より大きい値の区分と小さい値の区分に振り分ける操作を、各区分で繰り返す整列法です。

ウ：バブルソートは、隣り合う要素を比較して、順序が逆なら入れ替える操作を繰り返す整列法です。

出典：平成28年度 秋期 応用情報技術者試験 問6