酒と泪とRubyとRailsと

Ruby on Rails と Objective-C は酒の肴です!

アルゴリズムの勉強: クイックソート、マージソート[AOJ 10029][Ruby]

今回は、『AOJ 10029 - ソートアルゴリズム(クイックソート、マージソート)』についての記事です。

勉強のためにクイックソートと、マージソートを書いてみました。一般的にはマージソートよりもクイックソートの方が高速です。しかし、AOJで実際にプログラムを書いて実感しましたが、『クイックソートのアルゴリズムはソート対象によって計算量が変わる』ので、計算量が安定しているという意味では、マージソートの方が優れていることを知りました。でもそれ以上に、Rubyの実装の方が安定かつ高速なので、普段からプラットフォームの恩恵にあずかっていることを実感しました!


クイックソートのRubyサンプルソース

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Array
  def quick_sort
    return self if length <= 1
    base = pop
    smaller, bigger = partition { |e| e < base }
    push base
    smaller.quick_sort + [base] + bigger.quick_sort
  end
end

n = gets.to_i
arr = gets.split(' ').map(&:to_i)

puts arr.quick_sort.join(' ')

マージソートのRubyサンプルソース

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Array
  def merge_sort
    tmp = self.dup
    return tmp if tmp.length <= 1
    a, b = self.half.map { |e| e.merge_sort }
    marge(a, b)
  end

  def half
    mid = length/2
    return slice(0...mid), slice(mid..-1)
  end

  def marge(a, b)
    res = []
    until a.empty? and b.empty?
      res <<
          case
            when a.empty? then b.shift
            when b.empty? then a.shift
            when a.first > b.first then b.shift
            else a.shift
          end
    end
    res
  end
end

n = gets.to_i
arr = gets.split(' ').map(&:to_i)

res = arr.merge_sort
puts res.join(' ')

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

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

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

比較結果は次の通り。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
##################################################
sample = (0..100000).sort_by { rand }

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 = (1..1000).map{ (0..100).sort_by { rand } }.flatten

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)

マージソートはどちらも安定していますが、クイックソートは入力の配列に寄っては計算量がかなり増加しています。これはクイックソートが入力の配列によっては、1:N-1のソートを繰り返すためとのこと。

クイックソート - Wikipedia

マージソート - Wikipedia

ちなみに、RubyのCでのソートアルゴリズムもクイックソートだそうですが、この辺りもきちっと考慮されているようです。こういった部分も普段からRuby(言語開発者の方々)の恩恵に預かっているんだなぁ^^;

Aizu Online Judgeのサンプルソース

当面はAOJを解きながら、アルゴリズムの再勉強をしていくつもりです。Ruby/PythonでのAOJの回答は下のリポジトリに保存しておきます。もしツッコミとかあれば是非^^

morizyun/aoj-ruby-python - GitHub

最近解いたAOJの問題

AOJタグのついた最近解いた問題一覧

Special Thanks

Rubyでソート・アルゴリズムを表現しよう!

Rubyでクイックソート - Qiita

おすすめの書籍