Rubyでバブルソートとマージソートを比較する

概要

手習いのためにバブルソートとマージソートを書いて比較します。
先日、某codilityで最悪の場合に$O(n \log n)$でソートすることが求められて、マージソート（の変則）を書こうとしたら、ちょっと時間がかかったので。
具体的には、Arrayを受け取り、破壊的な操作をして、ついでにArrayを返す関数を書いて、比較します。

バブルソート

Wikipediaにおける説明
昔はもうちょっと浮き上がる感じのgifだったような。泡が浮き上がっていくイメージのソートアルゴリズムですが、たくさん比較、交換をしないといけないので遅いです。

bubble

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における説明
すべての要素を分割して、再帰的に結合＋ソート、結合＋ソート、…を繰り返していきます。再帰計算の例には、よく階乗やフィボナッチ数列が使われますが、マージソートでもよいような気がしています。

merge

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)$になります。厳密な計算については検索してみてください。

比較

compare

# 乱数列の作成
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の復習がてら、少し基礎的な勉強をして結果を書いていこうと思います。

おしまい

たのしめ！