クイックソート
9月 29th, 2007 admin
並んだ数のうち最初のものをとりあえずできるだけ奥のほうに移す、最後のほうをわかる限り左に移す。といった感じのクイックソート
一気に実行時間が短縮されました・・・
Rubyには++とか–はないらしい。10分ぐらいはまりました。
require 'pp' before = Time.now t = Time.now srand(t.sec ^ t.usec ^ Process.pid) Num = 10000 def quickSort(bottom, top, sort) if bottom >= top then return false end #先頭の値を「適当な値」とする div = sort[bottom] lower = bottom upper = top while lower<upper while(lower <= upper and sort[lower] <= div) lower+=1 end while(lower<=upper and sort[upper] > div) upper-=1 end if lower < upper then temp = sort[lower] sort[lower] = sort[upper] sort[upper] = temp end end #最初に選択した値を中央にする temp = sort[bottom] sort[bottom] = sort[upper] sort[upper] = temp quickSort(bottom,upper -1,sort) quickSort(upper+1,top,sort) return sort end #ランダムな値の入った配列を作成 sort = Array.new Num.times{ sort.push rand(10000) } #ソート前の出力 pp sort sort = quickSort(0,Num-1,sort); #ソート後の出力 pp sort #処理時間 p Time.now - before
N=10000の時の実行速度は5.672秒でした。
」に乗り換えた。こっちの本は今でもお世話になる。
」というような専門の本が出ているので必ず読んでおいたほうが良いと思う。
」などの専用の本もでていますしね。CakePHPはフレームワークを知らない人からすると話が飛びすぎている気がします。（mod_rewriteとかGETパラメータの取得とか、ORマッパとか）
