soraなりの日々 - fc2 -

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

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


「感動したっ!!」←小泉さん風

コレ↓
[Sorting Algorithms]
http://www.cs.rit.edu/~atk/Java/Sorting/sorting.html

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

各ソートを視覚的に見れるデモ。
面白いのがquick sortがまんまその動き(←そりゃ、そうだろけど、、、)。
ここでもbubble sortは論外な動き。
つか、遅すぎっっ。

んで、あまりの早さに驚いたのがshear sortってやつ。
このソート知らんかった。。。
何個かわかれて同時にソートしてる風だったんで、
スレッドでも使ってるんかなと思ったんだけど、ソース見ると別にそうでもない風。

※ちょっと今回はよくよく調べて書いてないんで、まるっきり違うこと書いてるかも。。。
 まー、恥は若いウチにかいておけ、と。

同サイトにjavaのソースがついてるんで、それをc++に
マージしよかと思ってたんだけど、探したらココにあった↓

[Estrutura de Informação] ←なんて読むんだろ?
http://www.dei.isep.ipp.pt/~psousa/aulas/EstrInfo/
(※"19.EXEMPLO DE APLICAÇÃO PARA RESOLUÇÃO DO 1º TRABALHO"
  の下にある"11.Shear sort"のリンクにあるソース)

で、その↑のソースを参考にして、この前std::sortで使ったソース
組み込んで測定してみた。

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

...
9999
9999
10000
10000
5.460000秒
(要素数10000)

前回のstd::sortの場合は、0.040000秒
quick sortは、0.120000秒

・・・
・・・・・・
メッチャ遅いがな・・・orz

そりゃ、bubble sortの121.930000秒よりはマシではあるんだけど、、、

なんだこの違いはっ!!
まー、オイラのソースがおかしい可能性だってあるし、まだまだ調査が必要みたい。
(xcode上でデバッグした限りだと正常そうなんだけどなぁ)


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

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

コメント

コメントの投稿


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

トラックバック

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