マージソート

10月 2nd, 2007 admin Posted in Ruby, アルゴリズムとデータ構造 |

こんなことをやってるのが凄く恥ずかしくなってきたが続ける
マージソートも5秒台。クイックソートより安定しているそうだ（そりゃそうだ）
少なくともバブルソートからは脱出できて以前よりは幸せな気持ち

マージしているところのループが冗長な感じだなと思って本を見ていたらC言語のくせに僕の半分ぐらいの行数で済ませている。
グローバル変数を使ってるからできるのだろうか？？お酒の酔いがさめたら見直してみたい。

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

Num = 10000

def mergeSort(sort)
	length = sort.length
	if length <= 1 then
		return sort
	end

	halfPosition = length / 2

	#前半を入れる配列
	frontSort = Array.new
	halfPosition.times {
		frontSort.push(sort.shift)
	}

	frontSorted = mergeSort(frontSort)
	rearSorted = mergeSort(sort)

	#返すべき要素の数を数える
	loopNum = frontSorted.length + rearSorted.length

	result = Array.new

	#最初に比較する値
	r = rearSorted.shift
	f = frontSorted.shift

	loopNum.times{
		if r == nil
			result << f
			f = frontSorted.shift
			next
		end

		if f == nil
			result << r
			r = rearSorted.shift
			next
		end

		if r <= f
			result << r
			r = rearSorted.shift
			next
		end

		if f < r
			result << f
			f = frontSorted.shift
			next
		end
	}

	return result
end

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

#ソート前の出力
pp sort

sort = mergeSort(sort);

#ソート後の出力
pp sort

#処理時間
p Time.now - before