ヒープソート : アルゴリズム

ヒープソートは整列の対象となる配列の中でヒープ構造を構築しながら整列を行うアルゴリズムです。 整列させたい配列からヒープを構築して、そこから元の配列にコピーして整列を完了させるのではないのです。マージソートのように作業用の領域や、クイックソートのような再帰処理が必要ありません。 アルゴリズム分析 まずは以下のような手順ではないことを理解してください。 整列対象の配列から別領域にヒープを構築する ヒープから元の配列にデータをコピーする この方法だとヒープを構築する専用の領域が必要になります。 実際のヒープソートは以下のような手順です。整列対象の配列はN個のデータを持ち、インデックスは1からNとします。 整列対象の配列内にボトムアップでヒープを構築する 構築されたヒープの先頭要素[1]と最後の要素[N]を交換する 要素[1]から要素[N-1]でヒープを再構成する ヒープの先頭要素[1]と最後の