ヒープソートを実際にトレースしてみた

基本情報技術者試験の午後問題で、ヒープソートを用いて昇順にソートするプログラムが出題されたので、これを参考にトレースしたものを紹介したいと思います。

ちなみに、以下で紹介する基本情報試験の過去問は、本来であれば穴埋め問題として出題されているところをトレースの便宜上、あらかじめ埋めてありますので、「初見で過去問を一度解きたい」など考えておられる方はご注意ください。

出典：平成17年度 春期 基本情報技術者試験 午後 問4

https://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2005h17_1/2005h17h_fe_pm_qs.pdf

紹介したプログラムに従うと、

１. プログラム「InitHeap」でランダムに格納された整数をヒープ構造にする。

２. プログラム「MakeHeap」でヒープ構造となった配列内でデータが昇順となるようにソートをする。

といった流れになります。

今回は、実際にどのようにソートが行われるのかを追っていきたいので、１.の処理は省き、２.の処理についてのみ紹介したいと思います。（要するに、あらかじめヒープ構造となったものを昇順に整列していくわけです。）

前回の記事でも使用させて頂いた以下の数値例でソート処理、トレースを行っていきたいと思います。

今回、紹介させて頂いた問題のプログラムでは、ヒープと配列が連動しており、現在は、以下のように、ヒープ構造で整列している配列を昇順に整列していきます。（各配列について、上の行は要素番号、下の行は実際の実際の数値です。）

ソート処理を行っていくにあたっては、HeapSort内に記載されている「　/* 並び替え */　」の処理内が実行されます。

「　/* 並び替え */　」の処理内を見てみると、Idx に初期値として Num (プログラムの説明(4)①より、今回はNum=10とします)を代入し、Idxが1より大きい間、-1処理を繰り返しながらプログラムSwap, MakeHeapを行う流れとなります。

Idxに初期値を設定した直後の処理として、プログラムSwapで、配列[1]と配列[10]を入れ替えていますが、これは、配列[1]には、最大値が格納されているため（配列がヒープ構造のため）、ソート未完了部分の末尾である配列[10]に格納してやることで、昇順ソートの第一段階クリアということになります。

配列の入れ替えを行った後には、配列内のヒープとしてみなされる部分（配列[1]～配列[9]）のヒープ条件を満たしていないので、プログラムMakeHeapでヒープの再構築を行います。

配列[10]はソート完了要素となるので、配列[1]～配列[9]について、ヒープ条件を満たしているかを確かめていきます。

MakeHeapで行われる処理は以下の通りです。

１. MakeHeapの引数であるTop, Lastにそれぞれ1, 9(プログラム上では「Idx-1」)を設定する。

２*. 根の子にあたる要素番号（L, R）を設定し、配列[L], 配列[R]と根の値とを比較していく。ヒープ条件（根 > 子）を満たさない場合には、入れ替えを行う。

変数が多く出ていてるので、以下のようにまとめた上で、プログラムに沿って考えていくと、今回の場合は以下のようになります。

今回は、プログラム内の、R ≦ Last（後方の比較対象が配列範囲内である）, A[L] < A[R]（A[2]　 < A[3]である）, A[Top] < A[R]（5 < 9 で根よりも子の方が大きい）を満たすことから、MakeHeap内の一番初めの処理「　/* 右が大きい */　」の各条件に合致するので、プログラムSwap(Top, R)とMakeHeap(R, Last)を順に行っていきます。

Swap(1, 3)を行うと、根 < 子関係は満たされるものの配列[3]の子との大小関係が乱れる可能性があることからこれらに対して、再度MakeHeapを行うことでヒープの再構築を行っていきます。今回は、配列[3]の子との大小関係を満たしていない(not(5 < 6))ため、これらの配列の入れ替えも行います。

↓

３. MakeHeapの処理を終えたら、HeapSort処理内の「 / * 並び替え */ 」処理に戻り、Idx-1をIdxとして、Swap処理で根の値とIdxを入れ替えることで配列内の末尾から順に昇順ソート結果を格納していき, MakeHeap処理でヒープの再構築を行う。以降、Idxが１より大きい間、同様の処理を繰り返す。

*前回の記事で、ヒープを構築する際には、「一番下の要素の右から左へ、そして、その上の要素の右から左へ見ていき…」と説明しましたが、今回紹介しているプログラムMakeHeapでは、一番上の要素から見ています。その理由としては、プログラムInitHeapでヒープ構成を満たしたうえで、配列[1]と配列[ヒープ要素としての末尾]とを入れ替えており、ヒープ関係を調べるにあたっては、入れ替え後の根にあたる配列[1]とその子にあたる配列[2], [3]の大小関係を優先的に調べる必要があるためです。

それでは、ヒープソートプログラムの処理の流れを把握したところで、トレースも載せたいと思います。

なお、今回紹介したプログラムはある参考書で出会ったものですが、その参考書で「難易度高め」と記載されていた（自分も理解するために相当な時間を要しました）ので、実際にトレースを進めていくことで処理の流れを掴んでいくのが一番の早道かと思います。

著者：かわ