Pythonによるアルゴリズムクイックリファレンス：挿入ソート

アルゴリズムを考えるのは面白い。面白いが基礎も忘れるべからずという事で「アルゴリズムクイックリファレンス」をPythonでコーディングしようかと思う。

挿入ソート

第四章は小手調べ。ここで行うソートはリスト型とかのAPIに組み込んであることがほとんどで、明示的に書くことはまず無い。だが、あえてやってみるというのがいい。ベンチマークをとってみると標準より早い場合もあるので、使ってみる価値はあるかと。

この挿入ソートは配列を順番に見ていって値を比較し、値が大きいものは横にずれていってもらうという方式。アルゴリズムというより力技に近い。

実行時間はこんな感じ

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

##                        real    (total    = user    + sys)
default                 0.0594    0.0600    0.0600    0.0000
insertion               0.3498    0.3500    0.3500    0.0000

## Ranking                real
default                 0.0594  (100.0) ********************
insertion               0.3498  ( 17.0) ***

## Matrix                 real    [01]    [02]
[01] default            0.0594   100.0   588.8
[02] insertion          0.3498    17.0   100.0

defaultというのはlist#sort()を実行した結果で、今回の挿入ソートがinsertion。比較すると実行速度はdefaultにかなわない事がわかった。ベンチマークにはBenchmarkerを使った。

という事で、しばらくやってみよう