マージソート | アルゴリズム [AOJ 10029][Ruby/Java]

今回は、『AOJ 10029 - ソートアルゴリズム(マージソート)』についての記事です。RubyとJavaのサンプルソースを載せています。

🏀 概要

1. 未整列のデータ群を半分に分ける操作を繰り返す
1. データ群が分割できなくなったところで今度は分割データのマージを繰り返す
1. マージはデータが整列するよう行う

🐡 Rubyコード

class Array
  def merge_sort
    return self if length <= 1
    a, b = half.map(&:merge_sort)
    merge(a, b)
  end

  def half
    n = (length/2.0).floor
    return self[0...n], self[n..(length-1)]
  end

  private

  def merge(a, b)
    result = []
    while a.size > 0 || b.size > 0
      result << if a.empty? then b.shift
                elsif b.empty? then a.shift
                elsif a.first < b.first then a.shift
                else b.shift
                end
    end
    result
  end
end

_n = gets.to_i
puts gets.split(' ').map(&:to_i).merge_sort.join(' ')

😼 2つのサンプルを使って比較

2つのランダムな配列を使ってテストをします。2つのサンプルは次のように作成します。

* 0-100000の数字を100,000個、ランダムに並べる場合
* 0-100の数字を100,000個、ランダムに並べる場合

比較結果は次のとおり。

################################################## sampleコード

puts Benchmark::CAPTION
puts 'quick_sort: ' + Benchmark.measure { sample.quick_sort }.to_s
puts 'marge_sort: ' + Benchmark.measure { sample.merge_sort }.to_s
puts 'ruby_sort:  ' + Benchmark.measure { sample.sort }.to_s

# 0-100000の数字を100,000個、ランダムに並べる場合
# user     system      total        real
# quick_sort:   0.250000   0.000000   0.250000 (  0.253962)
# marge_sort:   0.340000   0.000000   0.340000 (  0.349896)
# ruby_sort:    0.020000   0.010000   0.030000 (  0.015256)

################################################## sampleコード

puts Benchmark::CAPTION
puts 'quick_sort: ' + Benchmark.measure { sample.quick_sort }.to_s
puts 'marge_sort: ' + Benchmark.measure { sample.merge_sort }.to_s
puts 'ruby_sort:  ' + Benchmark.measure { sample.sort }.to_s

# 0-100の数字を100,000個、ランダムに並べる場合
# user     system      total        real
# quick_sort:   4.490000   0.040000   4.530000 (  4.529826)
# marge_sort:   0.370000   0.010000   0.380000 (  0.371850)
# ruby_sort:    0.000000   0.000000   0.000000 (  0.006622)