クイックソート

9月 29th, 2007 admin Posted in Ruby, アルゴリズムとデータ構造 |

並んだ数のうち最初のものをとりあえずできるだけ奥のほうに移す、最後のほうをわかる限り左に移す。といった感じのクイックソート
一気に実行時間が短縮されました・・・
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秒でした。

One Response to “クイックソート”

  1. toyosystem | Rubyでアルゴリズムとデータ構造 Says:
    9月 29th, 2007 at 3:20:35

    [...] クイックソート [...]

Leave a Reply