msort.rb

30分シリーズ、その6。ネタ切れしたら、アルゴリズムの本を取り出せばいいことに気がついた。
ということで今回はマージソート。

$ ruby msort.rb
オリジナル:[41, 26, 21, 26, 53, 93, 33, 11, 37, 25]
正順ソート:[11, 21, 25, 26, 26, 33, 37, 41, 53, 93]
逆順ソート:[93, 53, 41, 37, 33, 26, 26, 25, 21, 11]

def merge(lhs,rhs,&block)
  return rhs if lhs.empty?
  return lhs if rhs.empty?
 
  cmp = block ? block.call(lhs[0],rhs[0]) : (lhs[0] <=> rhs[0])
  if cmp <= 0
    [lhs[0]] + merge(lhs[1..-1],rhs,&block)
  else 
    [rhs[0]] + merge(lhs,rhs[1..-1],&block)
  end
end
 
def msort(items,&block)
  return items if items.size == 1
 
  before = items[0...items.size/2]
  after  = items[items.size/2..-1]
 
  merge msort(before,&block),msort(after,&block),&block
end

# テストデータ生成
array = (1..10).map{
  rand(100)
}

# 表示
puts "オリジナル:#{array.inspect}"
puts "正順ソート:#{msort(array).inspect}"
puts "逆順ソート:#{msort(array){|a,b| b <=> a }.inspect}"

配列をリストとして扱おうとして、ところどころに無理がでてる。というか、標準ライブラリにリスト入れてくれないかな。