【アルゴリズム】【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"

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