DISTRICT 37

なにか

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

ベンチマークとしてはまだまだデフォルトにはかなわないながらも、挿入ソートよりは結果を出せた。とはいっても本当に誤差の範囲なので積極的に使おうとは思えない。効果が最大限に現れるときってどんな問題なんだろう。

アルゴリズムクイックリファレンス

アルゴリズムクイックリファレンス