Rubyでクイックソート

cf. RubyでクイックソートとRSpecでそのテストを書いてみる – 凸ろぐ

なんだかまどろっこしい書き方をしてるなあ。これでいいんじゃないか？

require 'benchmark'

class Array
  def qsort
    return self if self.size <= 1
    pivot = self.shift
    left = self.select{|x| x < pivot }
    right = self.select{|x| pivot <= x }
    return left.qsort + [pivot] + right.qsort
  end
end

ary = [1,2,3,4,5,6,7,8,9,10].shuffle
ary2 = ary.dup

Benchmark.bm(13) do |x|
  x.report("Array#sort: ") { ary.sort }
  x.report("Array#qsort:") { ary2.qsort }
end

takatoh@nightschool $ ruby qsort.rb
                    user     system      total        real
Array#sort:     0.000000   0.000000   0.000000 (  0.000006)
Array#qsort:    0.000000   0.000000   0.000000 (  0.000013)

Array#soft 速いな。やっぱり自前で作るよりあるものを使ったほうがいいってことか。
いや、リンク先の実装だと速いのか？

require 'benchmark'

class Array
  def qsort
    return self if self.size <= 1
    mark = self[0]
    right = Array.new
    left = Array.new
    (1..self.size-1).each do |i|
      if self[i] <= mark
        left.push(self[i])
      else
        right.push(self[i])
      end
    end
    left = left.qsort
    right = right.qsort
    return left + [mark] + right
  end
end

ary = [1,2,3,4,5,6,7,8,9,10].shuffle
ary2 = ary.dup

Benchmark.bm(10) do |x|
  x.report("Array#sort: ") { ary.sort }
  x.report("Array#qsort:") { ary2.qsort }
end

takatoh@nightschool $ ruby qsort2.rb
                 user     system      total        real
Array#sort:   0.000000   0.000000   0.000000 (  0.000006)
Array#qsort:  0.000000   0.000000   0.000000 (  0.000019)

そんなことはなかった。