11月 6th, 2007 admin 
次のソートに進みます。
今日はP17から。ソートには「安定性」という指標があるそうです。分かりにくい感じですが、本では「宛名書きソフト」を例に非常に分かりやすく説明してくれています。要するに「氏名を名でソートしてから性でソート」した場合に名のソート結果も保持してくれているのが安定したソート、そうでないのが不安定なソートということみたいです。
さて、今日コード書くコームソートというのはバブルソートの改良版のようなもので、バブルソートでは隣同士のデータを比較し1つずつ移動していくアルゴリズムだったものを隣同士ではなくある程度離れた(ギャップという)データを比較し交換していくというものです。
感覚的にもバブルソートよりはましなんだろうなという感じが伝わってきます。
require 'pp'
before = Time.now
t = Time.now
srand(t.sec ^ t.usec ^ Process.pid)
Num = 10000
def combSort(sort)
gap = Num
while gap != 1
gap = (gap * 10) / 13
flag = true
(Num-gap).times{|i|
if sort[i] > sort[i+gap] then
tmp = sort[i]
sort[i] = sort[i+gap]
sort[i+gap] = tmp
end
}
end
return sort
end
sort = Array.new
Num.times{
sort.push rand(Num)
}
pp sort
sort = combSort(sort);
pp sort
p Time.now - before
これで残るソートはあと3つ・・
※このシリーズは私がアルゴリズムとデータ構造を基礎から学ぶ記録です。全体の目次はこちらへ。