読者です 読者をやめる 読者になる 読者になる

せかいや

いまいるここを、おもしろく http://sekai-in-the-box.appspot.com/

【アルゴリズム】【Ruby】ソートのいろいろ ~バブルソート

Rubyでfor文ぐるぐる等を実行していたら師匠からメールが来た。

計算量って知ってる?
バブルソートって遅いよねっていうのは、
エクレアってデザートよねってくらいに常識かな。。ほんまに。

 
これはやばい流れだ・・・と思っていたら案の定、

まずは基本中の基本である
ソートはおさえたほうがいいよ
各種のソートの概要と計算量
んで、有名なソートのいくつか
バブル、クイックくらいは実装できるようにしたほうがいいよ

その後、リスト、グラフを理解すれば大体はいけるかな

「大体はいける」(白目)

 
自分が知っているレベルは

ソートっていろんな種類がある
遅いソート、早いソートがある

以上


それでは始めます。

Array#sortは何ソート?

Arrayクラスの実装はどうもこのクラスのよう↓
https://github.com/ruby/ruby/blob/trunk/array.c

この中のrb_ary_sort_bangメソッドで実装している。
が、何やってるのか良く分からない。
当然どういうアルゴリズムのソートをしているのか良く分からない。

ひとまず置いとこう。


ソートの「遅さ?」

まずはテストデータと、「処理時間(遅さ)」を計測するコードを書こう。

a = (0..999).to_a
data = a.sample(a.size) ←テストデータ

start_time = Time.now
# 実行したい処理
end_time = Time.now

p ("timeee " + (end_time - start_time).to_s + "s" ) ←時間計測


こんなところかな。

Rubyのsortメソッドの遅さ

a = (0..9999).to_a
data = a.sample(a.size)

start_time = Time.now
result = data.sort
end_time = Time.now

p result
p ("timeee " + (end_time - start_time).to_s + "s" )

■実行結果

[0, 1, 2, 3, 4,・・・
"timeee 0.004s"


別に遅くなくない?
メールを見返してみると、直接、Array#sortが遅いといっているわけではない。
私の勘違いか。
ループぐるぐるを怒ってるだけかな。

とりあえず、ソートを実装してみよう。

バブルソート

要素の1番目と2番目を比較し、順番が逆であれば入れ換える。次に2番目と3番目を比較して入れ換える。これを最後まで行うと、最後の数だけが最小または最大の数として確定するので、確定していない部分について1つずつ減らしながら繰り返す。

http://ja.wikipedia.org/wiki/%E3%83%90%E3%83%96%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88

やってみよう。
 
出来た。

a = (0..9).to_a
a = a.sample(a.length)

start_time = Time.now

i = 0
while i < a.length
	j = 1
	while j < a.length - i
		if a[i] > a[i+j] then
			a[i], a[i+j] = a[i+j], a[i]
		end
		j += 1
	end
	i += 1
end

end_time = Time.now

p a
p ("timeee " + (end_time - start_time).to_s + "s" )

■実行結果

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
"timeee 0.004s"

ふーん。遅いのかな。
次はクイックソートを実装しよう。