Tbpgr Blog

Employee Experience Engineer tbpgr(てぃーびー) のブログ

アルゴリズム | マージソート

内容

データを分割し、それぞれをソート後、結果をマージする。
分割統治法。最悪計算量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