퀵 정렬

https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

퀵 정렬은 병합 정렬과 동일하게 분할 정복을 사용하여 정렬 문제를 해결한다.

퀵 정렬의 특별한 점은 pivot이라는 개념을 사용하는데, 배열 요소 중 하나를 pivot으로 정하여 pivot보다 작은 값을 왼쪽으로 큰 값을 오른쪽으로 배치하고 분할된 두 영역에 다시 위 과정을 크기가 1이 될 때 까지 반복하여 마지막에 모두 합치면 정렬되는 방식이다.

퀵 정렬의 시간복잡도는 O(nlogn)이다. 

Big O notation은 알다시피 가장 최악의 상황에서의 시간복잡도를 표현하는데, 퀵정렬의 최악의 시나리오에서 시간복잡도는 O(n^2)이다. 하지만 퀵 정렬은 특별하게 pivot을 어떤 요소로 선택하느냐에 따라 성능이 변하게 되는데,  이를 통해 평균 적으로 O(nlogn)의 성능을 낼 수 있으므로 일반적으로 O(nlogn)로 말한다.

말했듯이 pivot 의 선택에 따라 성능이 달라지기 때문에 퀵 정렬에서는 pivot 선정이 매우 중요하다.
분할을 진행할 때 가능한 두 영역의 크기가 동일하게 분할하는게 성능에 좋다. 즉, pivot이 중위값에 근사할수록 유리하다.
하지만 정렬하기 전에는 어떤 값이 중위값인지 알 수 없으므로 선택되는 방법이 몇가지 있는데, 
그 예로
첫번째 또는 마지막 요소,
랜덤 요소,
세 랜덤 요소 중 가운데 값이 있다.