【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らしいコードだなと思う。
まだ書き慣れない・・。