Quick Sort최악의 경우 실행시간은 $O(n^2)$이다.평균적으로, 실행시간은 $O(n\lg{n})$이다. 이때의 숨겨진 상수 계수는 다른 알고리즘보다 작아서, 실제로는 매우 빠르게 동작하는 편이다. 퀵 정렬은 분할-정복 방식으로 작동한다.분할: 배열 A[q...r]을 피벗을 기준으로 두 개의 부분 배열로 나눈다. 앞 부분의 배열 A[p...q-1]의 모든 요소는 피벗 A[q] 보다 작거나 같고, 뒷 부분의 배열 A[q+1...r]의 모든 요소는 피벗 A[q]보다 크거나 같다.정복: 분할된 두 부분 배열을 재귀 호출을 통해 각각 정렬한다.결합: 퀵 정렬은 제자리 정렬이기 때문에, 두 부분 배열을 따로 결합할 필요는 없다.분할 과정은 PARTITION 이라는 절차를 이용해 이루어지며, 이 절차는 피벗..
