単純挿入ソート（2分挿入ソート）
11月 27th, 2007 admin Posted in Ruby, アルゴリズムとデータ構造 | 
今日は単純挿入ソートです。
前から順にひとつずつ値をチェックしていき、自分より前方に自分より大きな値があればそこに値を挿入するというもの。
直感的にも明らかに遅い感じだし、実際に計算量オーダはO（N^2）なのですが、ほとんど整列が終わっているデータに対しては大変効率がよいということです。
#単純挿入ソート require 'pp' before = Time.now t = Time.now srand(t.sec ^ t.usec ^ Process.pid) #ソートする要素数 Num = 10000 def simpleSort(sort) (Num-1).times{|sorted| #ソート済みでない値を取り出す insert = sort[sorted+1]; #挿入する場所を見つける for i in 0..sorted if sort[i] > insert then break end end if i == sorted then next end #ソート済み領域直後の値を挿入する while i <= (sorted + 1) temp = sort[i] sort[i] = insert insert = temp i+=1 end } return sort end #ランダムな値の入った配列を作成 sort = Array.new Num.times{ sort.push rand(Num) } #ソート前の出力 pp sort sort = simpleSort(sort); #ソート後の出力 pp sort #処理時間 p Time.now - before
Num=10000で実行してみると僕の環境では70秒程度かかる。バブルソートよりは早いということですかね。
2分挿入ソート
単純挿入ソートの改良版で2分挿入ソートというのがあるそうです。上記の「挿入する場所を見つける」という部分をバイナリサーチというのを使って改良したものだということです。バイナリサーチについては第2章で取り扱うということなのでとりあえず省略します。
※このシリーズは私がRubyでアルゴリズムとデータ構造を基礎から学ぶ記録です。全体の目次はこちらへ。
11月 27th, 2007 at 3:56:00
[...] 単純挿入ソート（2分挿入ソート） [...]