概要
内容
データを分割し、それぞれをソート後、結果をマージする。
分割統治法。最悪計算量O(n log n)
コード
merge_sort.rb
# encoding: utf-8 class Array def merge_sort s = self.size return self if s == 1 lesses = self.pop(s >> 1) merge_for_sort(self.merge_sort, lesses.merge_sort) end private def merge_for_sort(lesses, largers) less_index = 0 lesses_size = lesses.size ret = [] total = 0 largers.each do |large| is_set_large = false (less_index..lesses_size - 1).each do |j| less = lesses[j] if large < less ret << large is_set_large = true total += 1 break else ret << less less_index += 1 total += 1 end end unless is_set_large ret << large total += 1 end end unless less_index == lesses_size (less_index..(lesses_size- 1)).each do |k| ret[total] = lesses[k] total += 1 end end ret end end
テストコード
merge_sort_spec.rb
# encoding: utf-8 require_relative "../merge_sort" describe Array do cases = [ { input_ary: [5,4,3,2,1], expected: [1,2,3,4,5] }, { input_ary: [1,2,3,4,5], expected: [1,2,3,4,5] }, { input_ary: [1,4,3,2,5], expected: [1,2,3,4,5] }, { input_ary: [2,4,3,5,1], expected: [1,2,3,4,5] }, { input_ary: [3,4,5,2,1], expected: [1,2,3,4,5] } ] cases.each do |c| it "#merge_sort" do actual = c[:input_ary].merge_sort expect(actual).to eq(c[:expected]) end end end