ソートアルゴリズム
昨日に引き続き、改良を加えてみた。昨日書いた通りに構造体に重複数を加えたら、重複する場合もの凄く高速化はした*1が、ちょっとオーバーヘッドが大きい*2。そこで重複した際にはバイナリツリーの右下を参照して、右下も同じ値ならばその右下の左に差し込むようにしてみた。こうするとオーバーヘッドも少ないし、重複時には前者程でないにしろ高速化するようになった。
でもやっぱり、クイックソートとか使ったほうが速いよなぁ…。このアルゴリズムが使えそうなんは、新しいアイテムがちょくちょく追加される度にソートし直す場合とかかなぁ…。ヒープソートみたいにツリーを消す必要が無いのを利用して、ツリーを保持しとけば高速になると。
