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  # 2502.999 MHz
## parameters:          loop=1000, cycle=1, extra=0

##                        real    (total    = user    + sys)
default                 0.0487    0.0500    0.0500    0.0000
insertion               0.3325    0.3300    0.3300    0.0000
median                  0.3296    0.3300    0.3300    0.0000
quick                   0.1864    0.1800    0.1800    0.0000

## Ranking                real
default                 0.0487  (100.0) ********************
quick                   0.1864  ( 26.1) *****
median                  0.3296  ( 14.8) ***
insertion               0.3325  ( 14.7) ***

## Matrix                 real    [01]    [02]    [03]    [04]
[01] default            0.0487   100.0   382.5   676.5   682.3
[02] quick              0.1864    26.1   100.0   176.9   178.4
[03] median             0.3296    14.8    56.5   100.0   100.9
[04] insertion          0.3325    14.7    56.1    99.1   100.0

ベンチマークとしてはこんな感じ。これまでやってきたアルゴリズムよりはだいぶ早い。改良版の名前はダテじゃなくオリジナルである中央値ソートに1.8倍の差を見せつけているが、defaultに4倍の差ではなされ、まだまだ牙城を崩せそうにない。これだけのコードで結果が出るのでアルゴリズムのパワーを感じる。

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

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