soraなりの日々 - fc2 -

こころにひっかかったもの

コードの中心でiをさがす -続々sort編-


こんな続くとは思ってもおらず、、、
何の気なしに前回「続」ってしてたら段々破綻してきてる気がする。。
とりあえず、「続々」ってことで。

今度は15個のデモが見れるやつ↓

[Sorting Algorithms]
http://cg.scs.carleton.ca/~morin/misc/sortalg/

このエントリーをはてなブックマークに追加

操作は前回紹介したデモのやつと同じなんだけど、
上のやつはソートの種類が15個と数が増えとります。
んで、さっそく速度を測るんだけど、全部やるのはシンドイんで
適当に動かしてみて早かったmerge sortで試すことにする。

サイトの下のリンク先にjavaのソースがあるのでそれをc++に変換。
って言っても大したことしてなくて、ほとんどそのままでOK。
(c++のソースほしい人はコメントください)

...
998
999
1000
0.010000秒
(要素数1000)

...
9996
9996
10000
0.100000秒
(要素数10000)

...
99995
99996
99997
0.890000秒
(要素数100000)

うおっ!さすがに早ぇぇ。

前々回の時のstd::sortは、要素数10000で0.040000秒
quick sortでは、要素数10000で0.120000秒

要素にstd::vector使ってるからかもしれないけど、std::sort早いな。
んで、std::sort使えない状況なら、merge sortで決まりかな。いまんとこ。

しかし、merge sort とquick sortだとmergeのが早いのね。
wikipediaではquick sortの方が早いそうなんだが、、、

なんかオレ間違えてる??


環境:PowerBook G4 1.25 GHz memory 1 GB
  :gcc version 4.0.1 (Apple Computer, Inc. build 5363)


関連記事:
コードの中心でiをさがす -続sort編-
コードの中心でiをさがす -sort編-
このエントリーをはてなブックマークに追加

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

トラックバックURLはこちら
http://sora2hs.blog70.fc2.com/tb.php/87-3fe881e0
この記事にトラックバックする(FC2ブログユーザー)