もう7月ナリね。みなさん、空の色は何色でしょうか。

8月下旬の院試が近づいてきてるので、当職は過去問をモリモリ消化している最中ナリ。

本日当職が解いた問題でアルゴリズムの問題にヒープソートに関する問題が出て、それも回答形式がCライクな擬似コードとあったので、
「楽勝ナリ。当職を舐めるでないナリ」とか思ってましたを。ヒープソート自体は図解が非常にわかりやすく、こんなもん実際に構造体で二分木作ったらすぐ終わるとタカくくってたナリよ。
しかしいざコードを書いてみると、新しいノードを追加しようとしたときに、最下層で子を持た無いノードを常に把握するためには、どうしてもその子無しノードへのポインタを常に保持する必要が出るナリ。

コードは出来たナリ。でも全く当職の肢体のごとく非常に醜いコードだったナリ。
そもそも院試で擬似コードを使って書け、という場合はもっとシンプルなはずナリ。

これはいけない。
ということで、ヒープのwikiを見たら、なんと配列を使って実装できてしまうものだったナリね……。

ある配列で2分木を表す場合、現在参照している要素nの子は2nと2n+1、という性質を使っているのですを。
これは経験的にはわかるナリけど、どうしても証明したかったからゴリゴリ計算したナリ。

2^n inf){n! / n^n} = n!　を満たす必要がある

2^m >= n!……(2)
m >= log n!

ここで
lim(n->inf){(log n! )/(log n^n)} =O(log n^n)
m>=O(n log n)

こういう議論からソートの理論限界値があるナリけど、なんかネットで資料みても(1)と(2)だけ使ってO(nlogn)出してるところが多いナリ。
オーダー記号に対してlogをとるというのは明確にルールがないのだから、もうちょっと定義にしたがって書いて欲しかったナリね。


声なき声に力を。無法地帯に核を。コメント無きコードに罰を。

・「C言語によるアルゴリズムとデータ構造」(ISBN978-4797320930)
・「新・明解C言語によるアルゴリズムとデータ構造」(ISBN978-4797366242)
のプログラムは参考になります。

筆者は同じです。

>>naohiro19 さん

おほーっ！これはいわゆるアルゴリズム集ですか。
自分は大学の教科書だけ使っていたので図書館で覗いてみようとおもいますを。

心優しい方に感謝を。