クイックソート(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 を使うのはちょっと反則な気もする・・・。