せかいや

いまいるここを、おもしろく http://sekai-in-the-box.appspot.com/

【Ruby】マージソート

マージソートとは

データ列を分割する(通常、等分する)
各々をソートする
二つのソートされたデータ列をマージする

http://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88

やってみよう。
 

Wikiを見ながら、、

a = (1..5).to_a.shuffle!

def merge_sort(a)
  return _merge_sort a.dup
end

def _merge_sort(lst1)
  return lst1 if lst1.length <= 1
  lst2 = lst1.pop(lst1.length / 2)
  return _merge_(_merge_sort(lst1), _merge_sort(lst2))
end

def _merge_(lst1, lst2)
  len1, len2 = lst1.length, lst2.length
  i, j, k= 0, 0, 0
  result = Array.new(len1 + len2)
  a, b = lst1[0], lst2[0]
  loop {
    if a < b
      result[i] = a
      j += 1 ; i += 1
      break if j >= len1
      a = lst1[j]
    else
      result[i] = b
      k += 1 ; i += 1
      break if k >= len2
      b = lst2[k]
    end
  }
  while j < len1
    result[i] = lst1[j]
    i += 1 ; j += 1
  end
  while k < len2
    result[i] = lst2[k]
    i += 1 ; k += 1
  end
  result
end

p merge_sort(a)


うーんなるほど。
さすがにWikiのコードはloop while の使い方が上手いなあ。
勉強になりました。

 
Rubyの文法を活用して実装しているサイトもありました↓

class Array
  def merge_sort
    tmp = self.dup
    return tmp if tmp.length <= 1
    a, b = self.half.map { |e| e.merge_sort } ←(2)
    merge(a, b)
  end
  def half
    mid = length/2
    return slice(0...mid), slice(mid..-1)  ←(1)
  end
  
  def merge(a, b)
    res = []
    until a.empty? && b.empty?
      res <<
        case
        when a.empty? then b.shift
        when b.empty? then a.shift
        when a.first < b.first then a.shift
        else b.shift
        end
    end
    res
  end
end

(1)と(2)がRubyらしいコードだなと思う。
まだ書き慣れない・・。