日々の破片

_ マージソート

思考する機械コンピュータ (サイエンス・マスターズ)(ダニエル ヒリス) まだ、続きを読んでいるわけだが、

このアルゴリズム（マージソート）では、対象物を二つのグループに分割し、各グループの要素を一つずつ順繰りに取り出しては、昇順に揃える操作を繰り返し、その結果をマージしたものを再びマージの対象にするサブルーチンが再帰的に呼び出される（これでは簡単すぎてうまくいく訳がないとお疑いになる読者は、ご自分で試してみるのも一計である

自分で試すも何もさっぱりわからない説明だ。が、いろいろ考えて、次のようなのができた。これで良いのかな？

NUM_OF_ELEMENTS = 16
o = []
1.upto(NUM_OF_ELEMENTS) do |x|
  o << (rand * NUM_OF_ELEMENTS).to_i
end
p o
 
def m(o0, o1)
  if o0.empty?
    o1
  elsif o1.empty?
    o0
  else 
    [((o0[0] > o1[0]) ? o1.shift : o0.shift)] + m(o0, o1)
  end
end
 
def s(o)
  if o.size > 1
    m(s(o[0...(o.size / 2)]), s(o[(o.size / 2)..-1]))
  else
    o
  end
end
 
p s(o)

実行するとこんな感じ。

$ ruby -d msort.rb
[7, 7, 0, 2, 13, 9, 15, 7, 7, 15, 7, 10, 3, 0, 7, 8]
[7, 7]
[0, 2]
[0, 2, 7, 7]
[9, 13]
[7, 15]
[7, 9, 13, 15]
[0, 2, 7, 7, 7, 9, 13, 15]
[7, 15]
[7, 10]
[7, 7, 10, 15]
[0, 3]
[7, 8]
[0, 3, 7, 8]
[0, 3, 7, 7, 7, 8, 10, 15]
[0, 0, 2, 3, 7, 7, 7, 7, 7, 7, 8, 9, 10, 13, 15, 15]
[0, 0, 2, 3, 7, 7, 7, 7, 7, 7, 8, 9, 10, 13, 15, 15]

(追記：mをちょっと直した（ら、sも直すことになった（ら、デバッグ出力できなくなったので、実行例は嘘になった））。こういう意味かなぁ)