クイックソート

am

Rubyでクイックソートを作ってみました。シンプルな仕上がり♪

  • qsortとqsort!を作りました。
  • 比較関数をブロックで与えることができます。
  • 与えられなかったら<=>を使います。
  • 課題: callではなくyieldを使う版
  • 課題: 非再帰版
class Array
  def qsort(&cmp)
    self.dup.qsort!(&cmp)
  end

  def qsort!(&cmp)
    cmp ||= lambda { |a, b| a <=> b }
    sort_between(0, length - 1, &cmp)
  end

  def sort_between(low, high, &cmp)
    return self if high <= low
    pivot = self[(low + high) / 2]
    left = low
    right = high
    loop do
      left += 1 while cmp.call(self[left], pivot) < 0
      right -= 1 while cmp.call(pivot, self[right]) < 0
      break if right <= left
      self[left], self[right] = self[right], self[left]
      left += 1
      right -= 1
    end
    sort_between(low, left - 1, &cmp)
    sort_between(right + 1, high, &cmp)
  end

  private :sort_between
end

a0 = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]

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

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

a2 = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
a2.qsort! { |a, b| b <=> a }
p a2        #=> [9, 6, 5, 5, 4, 3, 3, 2, 1, 1]

追記：rucilaさんの分散版クイックソートだそうです。何だかすごいですね♪