병합 정렬처럼 빠른 정렬도 분할 정복(divide-and-conquer) 전략을 사용하는 재귀 알고리즘 입니다. 빠른 정렬에서 분할 정복 전략을 사용하는 방법은 병합 정렬에서 사용하는 방법과는 약간 다릅니다. 병합 정렬은 분할 단계에서 거의 아무 것도 하지 않고, 모든 중요한 작업은 결합 단계에서 일어납니다. 빠른 정렬은 반대인데, 모든 중요한 작업은 분할 단계에서 일어납니다. 사실 빠른 정렬은 결합 단계에서 정말 아무 것도 하지 않습니다.
빠른 정렬은 병합 정렬과 다른 점이 몇 가지 있습니다. 빠른 정렬은 제자리에서 수행됩니다. 그리고 최악의 경우에 대한 수행 시간은 선택 정렬이나 삽입 정렬처럼 Θ(n2) \Theta(n^2) 로 좋지 않습니다. 하지만 빠른 정렬의 평균 수행 시간은 병합 정렬만큼 좋은 Θ(nlgn) \Theta(n \lg n) 입니다. 병합 정렬과 비슷한 성능을 보이는데 빠른 정렬을 고려하는 이유는 무엇일까요? 그것은 big-Θ 표기법 속에 숨겨진 빠른 정렬의 상수항이 꽤 괜찮기 때문입니다. 실생활에서 빠른 정렬은 병합 정렬보다 성능이 좋으며, 선택 정렬과 삽입 정렬보다 성능이 훨씬 뛰어납니다.
이제 빠른 정렬이 어떻게 분할 정복을 이용하는지 알아보겠습니다. 병합 정렬에서 했던 것 처럼, 최초의 하위 배열이 array[0..n-1]인 하위 배열 array[p..r]을 정렬한다고 생각해 봅시다.
  1. Divide by choosing any element in the subarray array[p..r]. Call this element the pivot. Rearrange the elements in array[p..r] so that all other elements in array[p..r] that are less than or equal to the pivot are to its left and all elements in array[p..r] are to the pivot's right. We call this procedure partitioning. At this point, it doesn't matter what order the elements to the left of the pivot are in relative to each other, and the same holds for the elements to the right of the pivot. We just care that each element is somewhere on the correct side of the pivot.
    As a matter of practice, we'll always choose the rightmost element in the subarray, array[r], as the pivot. So, for example, if the subarray consists of [9, 7, 5, 11, 12, 2, 14, 3, 10, 6], then we choose 6 as the pivot. After partitioning, the subarray might look like [5, 2, 3, 6, 12, 7, 14, 9, 10, 11]. Let q be the index of where the pivot ends up.
  2. Conquer by recursively sorting the subarrays array[p..q-1] (all elements to the left of the pivot, which must be less than or equal to the pivot) and array[q+1..r] (all elements to the right of the pivot, which must be greater than the pivot).
  3. Combine by doing nothing. Once the conquer step recursively sorts, we are done. Why? All elements to the left of the pivot, in array[p..q-1], are less than or equal to the pivot and are sorted, and all elements to the right of the pivot, in array[q+1..r], are greater than the pivot and are sorted. The elements in array[p..r] can't help but be sorted!
    Think about our example. After recursively sorting the subarrays to the left and right of the pivot, the subarray to the left of the pivot is [2, 3, 5], and the subarray to the right of the pivot is [7, 9, 10, 11, 12, 14]. So the subarray has [2, 3, 5], followed by 6, followed by [7, 9, 10, 11, 12, 14]. The subarray is sorted.
탈출 조건은 병합 정렬에서와 같이 요소가 2개 미만인 하위 배열이 됩니다. 병합 정렬에서는 아무것도 없는 하위 배열이 없었지만, 빠른 정렬에서는 만일 하위 배열 내의 다른 요소들이 모두 피벗 값 보다 작거나 모두 클 경우 아무것도 없는 하위 배열이 있을 수 있습니다.
정복 단계로 돌아가서 하위 배열의 재귀적 정렬을 다시 살펴 봅시다. 첫 번째 파티셔닝 후 피벗값은 6이고 [5, 2, 3] 과 [12, 7, 14, 9, 10, 11] 로 된 하위 배열이 생깁니다.
하위 배열 [5, 2, 3] 을 정렬하기 위해 3을 피벗값으로 선택합니다. 파티션을 나눈 후에는 [2, 3, 5] 가 됩니다. 피벗의 왼쪽에 있는 하위 배열 [2] 은 재귀 시 탈출 조건이 됩니다. 마찬가지로 피벗의 오른쪽에 위치한 하위 배열 [5] 도 그렇습니다.
하위 배열 [12, 7, 14, 9, 10, 11] 을 정렬하기 위해 11을 피벗값으로 선택하면 피벗의 왼쪽에는 [7, 9, 10] 가 위치하고 오른쪽에는 [14, 12] 가 옵니다. 하위 배열이 정렬 되면 [7, 9, 10] 다음에 11, 그리고 [12, 14] 가 놓이게 됩니다.
아래 그림에 빠른 정렬 알고리즘의 전체 진행과정을 나타냈습니다. 파란색으로 표시된 배열의 위치에는 이전 재귀 호출에서 피벗이 있었던 자리이므로 이 위치에 있었던 값들을 다시 검사하거나 이동시키지 않습니다:
퀵 정렬

위 자료는 다트머스 대학교 컴퓨터공학과토마스 콜먼 교수와 데빈 발컴 교수, 그리고 칸아카데미 컴퓨팅 과정 팀이 공동으로 저술했으며, 본 내용물의 저작권은 CC-BY-NC-SA 라이선스를 적용합니다.