Pythonによるアルゴリズムクイックリファレンス:選択ソート
選択ソート
これも力技の一種。曰く、整列アルゴリズムの中で最も性能が悪いので詳しく述べるのはやめるとの事。確かにこれに関して割いたページ数は2ページ(半ページ2枚なので実質1ページ)と扱いが小さい不遇なアルゴリズム。
未ソート分の中から最小値を探し、それを先頭のデータと交換するという処理。数列がどんな状態であろうと最後まで同じ処理を繰り返すので性能が悪いというのがわかる。
## 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 # 2497.120 MHz ## parameters: loop=1000, cycle=1, extra=0 ## real (total = user + sys) default hello 0.0443 0.0500 0.0500 0.0000 insertion 0.3179 0.3200 0.3200 0.0000 median 0.3209 0.3200 0.3200 0.0000 quick 0.1730 0.1700 0.1700 0.0000 select 0.2465 0.2500 0.2500 0.0000 ## Ranking real default 0.0443 (100.0) ******************** quick 0.1730 ( 25.6) ***** select 0.2465 ( 18.0) **** insertion 0.3179 ( 13.9) *** median 0.3209 ( 13.8) *** ## Matrix real [01] [02] [03] [04] [05] [01] default 0.0443 100.0 390.3 556.2 717.1 723.9 [02] quick 0.1730 25.6 100.0 142.5 183.7 185.5 [03] select 0.2465 18.0 70.2 100.0 128.9 130.2 [04] insertion 0.3179 13.9 54.4 77.6 100.0 100.9 [05] median 0.3209 13.8 53.9 76.8 99.1 100.0
おや?挿入ソートとか中央値ソートよりもベンチマーク出てるぞ?誰だ性能が悪いといったのは。1から100までの数列でテストしているので、これを1000までと延ばしたらどうだろうと試してみたが、やっぱり結果は中央値や挿入ソートよりも出る。 という事はこれまで書いたコードに何処かムダがあるのか?それともこのテストケースだから性能が出るのか?アルゴリズムって奥が深い。
- 作者: George T. Heineman,Gary Pollice,Stanley Selkow,黒川利明,黒川洋
- 出版社/メーカー: オライリージャパン
- 発売日: 2010/04/26
- メディア: 単行本(ソフトカバー)
- 購入: 11人 クリック: 656回
- この商品を含むブログ (68件) を見る