quick sortについて

quick sortは最も高速な探索アルゴリズムの一つ。 最速でO(n)ただ最悪の場合はO(n²)にもなりうる。 partitionと組み合わせて使用する。 partitionは数列のランダムな位置から１ヶ所要素を決める。これをpivotと呼ぶ。pivotを数列の右端に移動し、残りの要素と比較しする。pivotより大きい要素の場合は左側へ、小さければ右側へと分別する。pivotを基準に左右に分割された数列の中で、さらにそれぞれpivotを決める。それぞれの数列の中で同様にpivotを基準に要素を左右に振り分けていく。この作業を繰り返し、最後に分割された数列を統合する。