【Unity/C#】ヒープソートのアルゴリズムをC#で実装する

アルゴリズム、意識してますか？(挨拶)

前回、ヒープソートの準備として配列をヒープの構造に整理する処理を実装しました。

今回はヒープ構造から最大値(あるいは最小値)を選択して取り出すことでソートしていく、ヒープソートを実装します。

前回の記事はこちら。

エクスプラボ

【Unity/C#】ヒープソートのためのヒープ作り入門

https://ekulabo.com/algorithm-create-heap

ヒープソートの前段階として、配列をヒープ構造に変換する処理を実装します。初心者の頃はヒープってわかりにくかった記憶があるので、絵で解説してます。

環境

macOS 10.14 Mojave

Unity2018.3.14f1

Unity Hub 2.1.0

アルゴリズムって？

アルゴリズムとは何かという話は別記事で書いたのでそちらをご覧くださいな。

エクスプラボ

アルゴリズムってなんやいね？　って時に読む記事【初心者向け】

https://ekulabo.com/whats-algorithm

初心者のうちからアルゴリズムを理解し、処理時間を意識していくと、超イケてるプログラミングが可能になります。慣れてる人は多分無意識のうちにやっていることなんですよね。

ヒープって？

ヒープの説明や、配列をヒープ構造に整理する処理は前回の記事で書いたので、こちらもぜひご覧ください。

エクスプラボ

【Unity/C#】ヒープソートのためのヒープ作り入門

https://ekulabo.com/algorithm-create-heap

ヒープソートの前段階として、配列をヒープ構造に変換する処理を実装します。初心者の頃はヒープってわかりにくかった記憶があるので、絵で解説してます。

ヒープソートの流れ

ヒープソートは大きく分けて2段階の処理になっています。

まず、ソートしたい配列をヒープ構造に整理します。ここは前回ソースコードを解説付きで載せたのでそちらも合わせてご覧ください。

配列がヒープ構造になったら、今度は根をヒープから取り出す処理を実装します。

ヒープのルールでは、根はヒープ内の要素の最大値(または最小値)であるはずなので、これを順番に配列に詰めていけば自然とソートされた状態になります。例えば根が最大値になるなら、配列の後ろから順番にセットすることで昇順にソートされます。

根を取り出すとヒープの構造が変わるため、要素を入れ替えて新しくヒープを構成する処理が必要になります。なので、今回はまずこの処理を実装します。

その後、前回の処理と合わせてヒープソートとして実装することにしましょう。

根の削除

根を取り出す処理は「根の削除」と呼ばれることが多いです。

根の削除アルゴリズムを画像で説明します。

いま、以下のように大きさが4の配列があり、インデックスの小さな方から8, 4, 5, 1の数値が格納されているとします。この配列は既に『各ノードで親要素の値は子要素の値と同じかそれ以上となる』というルールのヒープ構造となっています。

まず最初に削除対象となるのはインデックス0の『8』です。今は根にいて、ヒープ内では最大値となっています。

この『8』をヒープから削除します。削除するといっても配列から消し去る訳ではなくて、同じ配列内でヒープと見なしている領域の最後尾の要素と入れ替えます。この場合は『8』と『1』を入れ替えます。『8』がいるインデックス3をヒープではない領域と考えて、ヒープを再構成します。

今根にいるのは『1』ですが、これは『各ノードで親要素の値は子要素の値と同じかそれ以上となる』というヒープのルールに反しているため、入れ替えを行います。子要素の中で『4』と『5』の比較を行うと、より大きな値は『5』なので、『1』と『5』を入れ替えます。

これでヒープが正しい状態になったので続けて根の削除を行っていきます。次は『5』の削除ですね。

『8』を削除した時と同様に、ヒープ領域の最後尾の要素と入れ替えることでヒープからの削除を表現します。結果として『8』を削除した直後と同じ形になっていますが、アルゴリズムで認識しているヒープ領域はインデックス0からインデックス1までとなっています。

また『1』が根に来てしまったので、『4』と交換を行います。これで正しいヒープ構造になりました。

次は『4』の削除です。ヒープ内の最後尾の要素である『1』と交換して削除を表現します。

ヒープ領域の要素が1つだけになったので、これをヒープ構造の外に出したと見なせば以下のようになります。

なんと、ソートされているではないですか。最大値を配列の後ろから並べたら、配列は昇順でソートされていることになりますね。

厳密に言えば『根の削除』は根となる要素を削除し、ヒープを再構成するところまでなのですが、削除した値の置き場所を工夫すればそのままソートになるんです。なるべく楽して目的を達成するのがアルゴリズムでは大切なのです。

ヒープソートを実装

これをC#で実装したコードがこちら。みっちりコメントを書いたので長くなってます。

今回作成したスクリプトは、ソートアルゴリズムで使っていた配列の中身を表示するためのメソッドを用意して継承しています。

SortBase.cs

こちらがヒープソートの本体です。200行近いソースコードを貼り付けるのもアレですが、こらえて下さい。

HeapSort.cs

配列の数値は特に意味はありません。ランダムなら何でも大丈夫です。

Start()の中でExecuteSort()を呼びます。このExecuteSort()はUpHeap()メソッドとDownHeap()メソッドを順番に実行します。

UpHeap()メソッドではソート対象の配列をヒープ構造として並べ替えています。

DownHeap()メソッドでその配列を使い、データを昇順になるように並べ替えます。

根とヒープ領域の最後尾の要素を入れ替えた後、GetBigChildIndex()の処理で子要素のインデックスを取得し、もし子要素があれば比較を行い、必要に応じて交換します。これはヒープが正しい形になるまで繰り返されます。

DownHeap()メソッドが完了すると、最初に与えられた配列がソートされた状態になります。

このスクリプトをアタッチしてゲームを実行すると、コンソールに処理結果が出てきます。

実行結果

出力結果を整形すると以下のようになります。

無事ソートされていました。

だんだんと値が小さくなる降順で並べ替えたい場合は、UpHeap()で根が最小値になるように並べ替えてください。DownHeap()の方でも根と子要素の比較で大小の条件を逆にする必要があります。

最悪計算時間、平均計算時間ともに\(O(n\log n)\)なので速いですね。

まとめ

今回はヒープソートのアルゴリズムをC#で実装しました。

ヒープは配列で表現できるので、思ったほど怖くないですね。やっぱり絵と配列が対応付けられていると理解しやすいです。

ヒープの法則性さえ分かれば実装は簡単なので、アルゴリズムに慣れてきたら挑戦してみてください。