コームソート
11月 6th, 2007 admin Posted in Ruby, アルゴリズムとデータ構造 | 
次のソートに進みます。
今日はP1７から。ソートには「安定性」という指標があるそうです。分かりにくい感じですが、本では「宛名書きソフト」を例に非常に分かりやすく説明してくれています。要するに「氏名を名でソートしてから性でソート」した場合に名のソート結果も保持してくれているのが安定したソート、そうでないのが不安定なソートということみたいです。
さて、今日コード書くコームソートというのはバブルソートの改良版のようなもので、バブルソートでは隣同士のデータを比較し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
これで残るソートはあと３つ・・
※このシリーズは私がアルゴリズムとデータ構造を基礎から学ぶ記録です。全体の目次はこちらへ。
11月 6th, 2007 at 2:12:07
[...] コームソート [...]