バブルソート
9月 29th, 2007 admin Posted in Ruby, アルゴリズムとデータ構造 | 
1,2,5,3,4,6
とデータが並んでいた場合に、
「1番目と2番目の数を比べる、比べて2番目の数が大きかったら数字を入れ替える」
「2番目と3番目の数を比べる、比べて3番目の数が大きかったら数字を入れ替える」
「N番目とN+1番目の数を比べる、比べてN+1番目の数が大きかったら数字を入れ替える」
というのを繰り返すのがバブルソートですね。
単純なのと引き換えに、最大でN^2回数字の比較をする必要があるのが難点です。
require 'pp' t = Time.now srand(t.sec ^ t.usec ^ Process.pid) Num = 10 def bubbleSort(sort) flag = true while flag flag = false (Num - 1).times{|m| if sort[m] > sort[m+1] then flag = true i = sort[m] sort[m] = sort[m+1] sort[m+1] = i end } end return sort end #ランダムな値の入った配列を作成 sort = Array.new Num.times{ sort.push rand(100) } #ソート前の出力 pp sort sort = bubbleSort(sort); #ソート後の出力 pp sort
N=10000の時 188.157秒かかりました。
ちなみにRubyで普通にやるなら
pp [1,3,2,4,2,5].sort
が正解だと思います。
こちらはN=10000の時 5.266秒かかりました。
さすが速い！というか僕のバブルが遅すぎる
9月 29th, 2007 at 2:07:01
[...] バブルソート [...]