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倍の差ではなされ、まだまだ牙城を崩せそうにない。これだけのコードで結果が出るのでアルゴリズムのパワーを感じる。
- 作者: George T. Heineman,Gary Pollice,Stanley Selkow,黒川利明,黒川洋
- 出版社/メーカー: オライリージャパン
- 発売日: 2010/04/26
- メディア: 単行本(ソフトカバー)
- 購入: 11人 クリック: 656回
- この商品を含むブログ (68件) を見る