クイックソート

Ruby

マージソートに引き続きクイックソートに挑戦してみた。

module Enumerable
  def qsort
    if size <= 1
      self
    else
      pivod = self[0]
      a, b = self[1..-1].partition{|i| i < pivod}
      a.qsort + [pivod] + b.qsort
    end
  end
end

[3, 1, 4, 1, 5, 9, 2, 6, 5, 3].qsort # => [1, 1, 2, 3, 3, 4, 5, 5, 6, 9]
[1, 1, 1, 1, 1].qsort                # => [1, 1, 1, 1, 1]
[1].qsort                            # => [1]
[].qsort                             # => []

Enumerable にはクイックソートのために作ったのかと思えるような partition というメソッドが存在する。

でも待てよ。
メモリをあまり使わないことも重要なんだよね。

という訳で qsort! に挑戦 ... と思ったら、ずいぶん前に書いてる人がいるな。

それを Enumerable のメソッドに変形。

module Enumerable
  def partition!(p, q)
    i = p
    (p+1 .. q).each do |j|
      if self[p] > self[j]
        i += 1
        self[i], self[j] = self[j], self[i]
      end
    end
    self[p], self[i] = self[i], self[p]
    i
  end

  def qsort!(p = 0, q = self.size-1)
    return self  if p >= q
    i = partition!(p, q)
    qsort!(p, i-1)
    qsort!(i+1, q)
    self
  end

  def qsort
    a = dup
    a.qsort!
  end
end

[3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5].qsort # => [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
a = (1..10).to_a.shuffle        # => [6, 8, 10, 2, 5, 7, 4, 3, 1, 9]
a.qsort!                        # => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

b = (1..10).to_a.shuffle        # => [9, 1, 2, 3, 10, 5, 7, 4, 8, 6]
b.qsort                         # => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
b                               # => [9, 1, 2, 3, 10, 5, 7, 4, 8, 6]

[1].qsort                       # => [1]
[].qsort                        # => []
[1, 1, 1, 1, 1].qsort           # => [1, 1, 1, 1, 1]
[1, 2, 3, 4, 5].qsort           # => [1, 2, 3, 4, 5]
[5, 4, 3, 2, 1].qsort           # => [1, 2, 3, 4, 5]
[1, 2, 1, 2, 1].qsort           # => [1, 1, 1, 2, 2]
[2, 1, 2, 1, 2].qsort           # => [1, 1, 2, 2, 2]