Pythonによるアルゴリズムクイックリファレンス:中央値ソート
中央値ソート
小手調べはまだ続く。今回のお題は中央値ソート。要素の真ん中の値を使って便宜的に二つの配列を作る。作った配列の真ん中の値を、、、と再帰的に処理を行って最終的にソートされる。いわゆる分割統治法で解決しているからか、さっそくアルゴリズムっぽくなってきた気がする。
しかし面倒くさくかつ汚いコードが出来上がってしまった。分割統治という考え方はともかく、このコーディングは今後しないだろうね。
## benchmarker: release 4.0.1 (for python) ## python version: 2.7.6 ## python compiler: GCC 4.8.2 ## python platform: Linux-3.13.0-48-generic-i686-with-Ubuntu-14.04-trusty ## python executable: /usr/bin/python ## cpu model: Intel(R) Core(TM) i5-4310U CPU @ 2.00GHz # 2710.412 MHz ## parameters: loop=1000, cycle=1, extra=0 ## real (total = user + sys) default 0.0513 0.0500 0.0500 0.0000 insertion 0.3031 0.3000 0.3000 0.0000 median 0.3016 0.3000 0.3000 0.0000 ## Ranking real default 0.0513 (100.0) ******************** median 0.3016 ( 17.0) *** insertion 0.3031 ( 16.9) *** ## Matrix real [01] [02] [03] [01] default 0.0513 100.0 588.1 590.9 [02] median 0.3016 17.0 100.0 100.5 [03] insertion 0.3031 16.9 99.5 100.0
ベンチマークとしてはまだまだデフォルトにはかなわないながらも、挿入ソートよりは結果を出せた。とはいっても本当に誤差の範囲なので積極的に使おうとは思えない。効果が最大限に現れるときってどんな問題なんだろう。
- 作者: George T. Heineman,Gary Pollice,Stanley Selkow,黒川利明,黒川洋
- 出版社/メーカー: オライリージャパン
- 発売日: 2010/04/26
- メディア: 単行本(ソフトカバー)
- 購入: 11人 クリック: 656回
- この商品を含むブログ (68件) を見る