クイックソート

クイックソートって両端から要素を調べて、入れ替えて..を繰り返すと思ってたけど
pivotより大きいものと小さいもので分けちゃえばそんなことしなくて済むのか。
それに、こうした方が再帰の考えが使いやすい。
これなら実装できそう。
なっとくアルゴリズムで分割統治法の考え方を説明されてやっと再帰がわかってきた。

def quick_sort(array)
  return array if array.length < 2
  pivot = array.shift
  low, high = array.partition{|num| num < pivot}
  quick_sort(low) + [pivot] + quick_sort(high)
end

クイックソートってこんなにシンプルだったのか。
関数として実装してるけど、Arrayのメソッドにすべきだったね。