“作ってわかるCプログラミング”でCを勉強 part2

pp.211-216 のヒープソートである。

main() から sort_heap()を呼び出して、その結果を表示している。
しかし、それはソートされていない。ヒープができただけのことである。
「* sort_heap() - ヒープをソートする」このコメントも間違っている。
この関数はヒープを作るだけである。make_heap() とでもしてほしいもんだ。

次に main() で remove_root()を n回呼び出して、ソート結果を
取り出している。表示が降順になるのはご愛嬌。
remove_root() は、例の sort_heap() を呼び出している。

ちょっと待ってくれ。

sort_heap() は内部に n/2 回のループを持っているから、O(n)。
そこから、heap() を呼び出していて、heap() は O(log n)。
だから、sort_heap() は O(n * long n)。
そうすると、main() から、remove_root() を n回呼び出しいるから、
ソート結果を得るのに、O(n * n * log n)。
これだと、O(n * n) の選択ソートや挿入ソートやバブルソートより
遅いじゃないか。

つまり、このプログラムはバグっているのである。
結果は正しく出るよ。でも、ヒープソートになっていない。

手っ取り早い修正方法は、remove_root() の中の sort_heap(--n_item);を
heap(1, --n_item) に置き換えることだろう。

しかし、ひどいソースである。私なら次のように書くね。

(続く)