クイックソート(quick sort)

疲れてきたのでコメント無し・・・。

def quick_sort(list)
  return list if list.length <= 1
  base = list.pop
  before = []
  after  = []
  list.each { |v|v <= base ? before.push(v) : after.push(v) }
  quick_sort(before) + [base] + quick_sort(after)
end

wikipedia みたら Array#partition を使ってた。初めてこのメソッド知った orz

def quicksort(list)
  return list if list.size <= 1
  pivot = list.pop
  left, right = list.partition { |e| e < pivot }
  quicksort(left) + [pivot] + quicksort(right)
end

他の言語と比べると記述量はダントツで少ないけど、pop や partition を使うのはちょっと反則な気もする・・・。