CLRSノート7:クイックソート

Quick Sortの原理は簡単で、典型的な分治法:
1、分
配列aは、要素xより小さいまたは等しいサブ配列と、要素xより大きい配列に分けられる
2、再帰
サブ配列再帰分
3、合
サブ配列が分かれたら順番にマージすればいい
RubyとErlangでQuick Sortを実現するのは本当に簡潔です.
ruby:

def quick_sort(a)
  (x=a.pop) ? quick_sort(a.select{|i| i <= x}) + [x] + quick_sort(a.select{|i| i > x}) : []
end

erlang:

quick_sort([]) ->
  [];
quick_sort([H | T]) -> 
  quick_sort([ X || X <- T, X < H ]) ++ [H] ++ quick_sort([ X || X <- T, X >= H ]).

最悪時間複雑度O(n^2):
分割するたびに選択される要素が最小または最大の値である場合、分割が完了すると、選択された要素以外のすべての要素の配列が空になり、複雑度が1+2+...+n = O(n^2)
最良の時間複雑度はΘ(nlogn):
分割するたびに選択される要素が中間値の場合、分割後の両側の配列sizeは同じ大きさになります.
T(n) = 2T(n/2) + Θ(n) = Θ(nlogn)