[정렬] 큌정렬 (Quick Sort)

* 퀵정렬 (Quick Sort)

"전체 원소에 대해서 정렬을 수행하지 않는다" 

- Divide and Conquer (분할 정복) : 재귀적 구현 필요

기준값(pivot) 을 중심으로 전체 원소들을 왼쪽 부분집합과 오른쪽 부분집합으로 분할(divide)

기준값(pivot) 보다 큰 원소는 배열의 오른쪽, 기준값(pivot) 보다 작은 원소는 배열의 왼쪽으로 이동

- 실행 성능은 선택한 기준값(pivot) 에 의해 결정

- 일반적으로 기준값(pivot) 은 전체 원소 중에서 가운데 위치한 원소를 선택

[시간 복잡도]

* 최선의 경우, 평균의 경우 : O(nlogn)

pivot 에 의해서 원소들이 왼쪽 부분집합과 오른쪽 부분집합으로 정확히 n/2개씩 이등분이 되는 경우가 반복

* 최악의 경우 : O(n^2)

pivot 에 의해 원소들을 분할했을 때 1개와 n-1개로 한쪽이 치우쳐 분할되는 경우가 반복

<퀵정렬은 같은 시간복잡도를 가지는 다른 정렬 방법에 비해서 자리 교환 횟수를 줄임으로써 실행 시간 성능 향상>