概要
手習いのためにバブルソートとマージソートを書いて比較します。
先日、某codilityで最悪の場合に$O(n \log n)$でソートすることが求められて、マージソート（の変則）を書こうとしたら、ちょっと時間がかかったので。
具体的には、Arrayを受け取り、破壊的な操作をして、ついでにArrayを返す関数を書いて、比較します。
バブルソート
Wikipediaにおける説明
昔はもうちょっと浮き上がる感じのgifだったような。泡が浮き上がっていくイメージのソートアルゴリズムですが、たくさん比較、交換をしないといけないので遅いです。
def bsort(a)
l = a.length
for i in 1..l do
for j in 1..(l-i) do
if a[j - 1] > a[j]
t = a[j]
a[j] = a[j - 1]
a[j - 1] = t
end
end
end
return a
end
コードは比較的すっきりしています。
配列の長さ(コード中のl)を$n$と書き直すと、ループの内容から明らかなように$n(n-1)/2$に比例した計算が必要になります。つまり$O(n^2)$です。
マージソート
Wikipediaにおける説明
すべての要素を分割して、再帰的に結合＋ソート、結合＋ソート、…を繰り返していきます。再帰計算の例には、よく階乗やフィボナッチ数列が使われますが、マージソートでもよいような気がしています。
def msort(a)
l = a.length
if l <= 1
return a
end
al = msort(a[0..((l-1)/2)])
ar = msort(a[((l+1)/2)..(l-1)])
i = 0
while i < l do
if al[0] < ar[0]
a[i] = al.shift
else
a[i] = ar.shift
end
i += 1
if al.length == 0
while i < l do
a[i] = ar.shift
i += 1
end
elsif ar.length == 0
while i < l do
a[i] = al.shift
i += 1
end
end
end
return a
end
ただ、マージソートの場合、バッファ領域みたいなものをきちんと意識して破壊的に書くか、適当にnewしまくるか、みたいな部分で色々気にしないといけないことが転がっています。ただ、その手の事情は良くも悪くも「実装する時には考えるべきこと」なので、それも含めた練習としては有意義かと思いました。
最悪の場合の計算のコストを$C(n)$で表すと、$C(2n)\leq C(n)+C(n)+2an$となりますが、これを順次適用して展開していくと、$2an,4a(n/2)=2an,8a(n/4)=2an,...$というように$2an$が$\log_2 n$個だけ出てきて、（たかだか）$O(n \log n)$であることが分かります。
※適当な説明…$C(n)+C(n)+2an$という式が、al,ar,後半のマージにそれぞれ対応していますが、マージは少なくとも$n/2$は比較が必要で、代入等は結局すべての要素について行うので、$O(n \log n)$になります。厳密な計算については検索してみてください。
比較
# 乱数列の作成
timearr.push Time.now.instance_eval { self.to_i * 1000000 + usec}
N = 10000
target = Array.new(N){0}
n = -1
temp = Array.new(N){n;n+=1}
n += 1
while n > 0 do
t = rand(n)
n -= 1
target[n] = temp[t]
temp.delete_at(t)
end
targeta = target.clone
targetb = target.clone
timearr.push Time.now.instance_eval { self.to_i * 1000000 + usec}
bsort(targeta)
timearr.push Time.now.instance_eval { self.to_i * 1000000 + usec}
msort(targetb)
timearr.push Time.now.instance_eval { self.to_i * 1000000 + usec}
p timearr[1] - timearr[0]
p timearr[2] - timearr[1]
p timearr[3] - timearr[2]
10000要素の無重複の乱数列を生成し、クローンを作って破壊的なソートを行います。
0 #準備の時間
5797493 #バブルソートの時間
31256 #マージソートの時間
これは圧倒的ですね。
rubyの配列の使い方の勉強も兼ねているのでdelete_atとかshiftとか、cloneの練習ができました。
アルゴリズムクイックリファレンスという書籍を買ったので、時間があれば、ruby/pythonの復習がてら、少し基礎的な勉強をして結果を書いていこうと思います。
おしまい
たのしめ！