せかいや

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

【アルゴリズム】【Ruby】ソートのいろいろ ~選択法 / 交換法 / 挿入法

「アルゴリズム 練習問題」で検索したらヒットする、
アルゴリズムに関して書いてあるサイト

を読んでいます。

選択法

一番小さい値を探す
それを一番上に書く
チェック済みだよと言う意味で、その値を消す(チェックする)
これを要素数分繰り返す

やってみよう

p a = (1..10).to_a.sample(10)
s = []
i = 0
while i < a.size
	min = a[i]
	j = 0
	while j < a.size
		if a[j] < min
			min = a[j]
			changed = j
		end
		j += 1
	end
	s << min
	a[changed] = 999
	i += 1
end
p s


■実行結果

[3, 8, 1, 9, 2, 10, 7, 5, 4, 6]
[1, 2, 3, 4, 5, 6, 7, 7, 8, 9]

ふーん。


 

交換法

選択法を少し発展させて、一番小さい値を消す(チェックする)のをやめ、 その選択された値と、それが入る順番の要素データを交換しながら処理することにする

やってみよう

p a = (1..10).to_a.sample(10)
i = 0
while i < a.size
	min = a[i]
	j = i + 1
	changed = -1
	while j < a.size
		if a[j] < min
			min = a[j]
			changed = j
		end
		j += 1
	end
	a[i] , a[changed] = a[changed] , a[i] if changed != -1
	i += 1
end
p a

 
■実行結果

[3, 6, 7, 10, 4, 2, 5, 8, 9, 1]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

ふーん。

 

挿入法

整列済みの配列に、次のデータを挿入していくと考える。
データの最後まで(次のデータがなくなるまで)繰り返す。

http://www5c.biglobe.ne.jp/~ecb/algorithm/6_a.html

なるほど。
やってみよう

 

a = (1..5).to_a.shuffle!
def insert_with_order(result, var)
	index = result.find_index{|item| item > var} || result.length
	result.insert(index, var)
end
result = a.inject([]) do |result, var| 
	insert_with_order(result, var)
end
p result

 
■実行結果

[8, 1, 7, 3, 9, 5, 6, 10, 4, 2]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

ふーん。
※以前記載していた方法は、誤実装(バブルソートだった)ので、取り下げました。
こちらのサイトを参考に実装しました。
hp12cさんの書くコードはいつも面白い。

ただ、この記事で紹介しているクイックソート

push base

は、不必要だと思うのだけれど。。。なぜ存在するのかな。。
散々hp12cさんには色々質問してるのでこれ以上聞けないけど、気になる><



クイックとバブルは前やったので省略。

ソート終わり。