はじめに
こんにちは
ふと、ヒープソートを実際に実装したことがなかったなと思い、C言語で実装することにしました。
本題
さっそくですが、コードは以下の通りです：
実装方針
以下を意識して実装しました
- 再帰
実装にあたり他のサイト様のコードをいくつか参考にさせていただきましたが、再起で実装されている方はあまりいらっしゃらないようでしたので、個人的趣味で再帰を利用して実装してみることにしました。
- 読みやすさ
理論を知っていればそのまま実装すれば良いため、あまり気にされる方も少ないかと思われますが、せっかくなので個人的に読みやすいコードにしました。(あくまで個人的にですが)
簡略フロー
- 木構造の(ソート済みでない)末端のノードを選ぶ。なければ手順5に進む。
- 選んだノードを親ノードとする。
- 親ノードとその子ノードを比較し、子ノードの方が大きければ入れ替える。
- 選んだノードの前のノードを選択し、手順2に戻る。前のノードがなければ次の手順に進む。
- 木構造の根と末端のノードを入れ替える。
- 木構造の末端のノードをソート済みとし、手順1に戻る。
- 終了
まとめ
選んだノードを親ノードとして、子ノードと入れ替える(ヒープ構造を作る)、というのに注目することで単純に実装できました。
ソート部分のみ再帰で書いたため、全て再起にするとより綺麗なコードになると思います。
おわり！