クイックソート

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秒でした。

Posted in Ruby, アルゴリズムとデータ構造 | 1 Comment »

バブルソート

9月 29th, 2007 admin

1,2,5,3,4,6
とデータが並んでいた場合に、
「1番目と2番目の数を比べる、比べて2番目の数が大きかったら数字を入れ替える」
「2番目と3番目の数を比べる、比べて3番目の数が大きかったら数字を入れ替える」
「N番目とN+1番目の数を比べる、比べてN+1番目の数が大きかったら数字を入れ替える」
というのを繰り返すのがバブルソートですね。
単純なのと引き換えに、最大でN^2回数字の比較をする必要があるのが難点です。

require 'pp'
t = Time.now
srand(t.sec ^ t.usec ^ Process.pid)

Num = 10

def bubbleSort(sort)
	flag = true
	while flag
		flag = false
		(Num - 1).times{|m|
			if sort[m] > sort[m+1] then
				flag = true
				i = sort[m]
				sort[m] = sort[m+1]
				sort[m+1] = i
			end
		}
	end

	return sort
end

#ランダムな値の入った配列を作成
sort = Array.new
Num.times{
	sort.push rand(100)
}

#ソート前の出力
pp sort

sort = bubbleSort(sort);

#ソート後の出力
pp sort

N=10000の時 188.157秒かかりました。

ちなみにRubyで普通にやるなら

pp [1,3,2,4,2,5].sort

が正解だと思います。
こちらはN=10000の時 5.266秒かかりました。

さすが速い！というか僕のバブルが遅すぎる

Posted in Ruby, アルゴリズムとデータ構造 | 1 Comment »

Rubyでアルゴリズムとデータ構造

9月 29th, 2007 admin

「どうせバブルソートしか知らないでしょ？」
え？なんて失礼なことを！･･･というわけで

プログラミングの宝箱 アルゴリズムとデータ構造 (C magazine)
プログラミングの宝箱 アルゴリズムとデータ構造 (C magazine)
posted with amazlet at 09.01.22
紀平 拓男 春日 伸弥
ソフトバンククリエイティブ
売り上げランキング: 11265
Amazon.co.jp で詳細を見る

を買いましたので、原文のC言語らしさとRubyの便利さの間で絶妙に妥協しながらやっていきたいとおもいます。
「とりあえずソートならRubyのArray.sortのソース嫁」
という考えも浮かびましたが･･･それはまた別のブログで・・・別の誰かが・・・

第1章　ソート

第2章　サーチ

第3章 リスト

第4章 スタック＆キュー

第5章 再帰呼び出し

第6章 ツリー構造

第7章 ハッシュとマップ

第8章 浮動小数点数と数値計算

第9章 文字列探索

第10章 バックトラック法と幅優先探索

Posted in Ruby, アルゴリズムとデータ構造 | 16 Comments »