ソートプログラム

昨日のC言語勉強会ではバブルソートと選択ソートをやったので、意欲を刺激されて例のC言語入門に書いてあったバイナリソート(？)を思い出しながら書いた。比較してみると、かなり速い。しかし、20000個程度でやけに遅くなる…と思ったら、バイナリツリーをルートから構築してるんで、データ重複が多いと異常に重くなるのは当然であって。というわけで、乱数の生成レンジを広くしたらそこそこ速くなった。
では、昨日小耳に挟んだクイックソートはどの程度速いんやろうか？と気になったので、適当に検索して引掛ったこのへん(Javaやけど)を見ながら色々やってみた。
4000,000個の乱数並び変えで約3.50秒…。マージソートも約3.55秒と速い*1。しかし自前バイナリソートは15秒超。一体この差は何や？と思ったが、やっぱツリー構築の際に手数がかかるんがネックよな…。読み出しは速いんやが。どっか間違っとるんかな…。なんとか速くしたいなぁ…。

追記：後で良く見たら、クイックソートのはずがマージソートと同じ関数で計測してた…。

*1:MobileAthlonXP2000+にて。