병합 정렬처럼 빠른 정렬도 분할 정복(divide-and-conquer) 전략을 사용하는 재귀 알고리즘입니다. 빠른 정렬에서 분할 정복 전략을 사용하는 방법은 병합 정렬에서 사용하는 방법과는 약간 다릅니다. 병합 정렬은 분할 단계에서 거의 아무 것도 하지 않고, 모든 중요한 작업은 결합 단계에서 일어납니다. 빠른 정렬은 반대인데, 모든 중요한 작업은 분할 단계에서 일어납니다. 사실 빠른 정렬은 결합 단계에서 정말 아무것도 하지 않습니다.
빠른 정렬은 병합 정렬과 다른 점이 몇 가지 있습니다. 빠른 정렬은 제자리에서 수행됩니다. 그리고 최악의 경우에 대한 수행 시간은 선택 정렬이나 삽입 정렬처럼 Θ(n2) \Theta(n^2) 로 좋지 않습니다. 하지만 빠른 정렬의 평균 수행 시간은 병합 정렬만큼 좋은 Θ(nlog2n) \Theta(n \log_2 n) 입니다. 병합 정렬과 비슷한 성능을 보이는데 빠른 정렬을 고려하는 이유는 무엇일까요? 그것은 big-Θ 표기법 속에 숨겨진 빠른 정렬의 상수항이 꽤 괜찮기 때문입니다. 실생활에서 빠른 정렬은 병합 정렬보다 성능이 좋으며, 선택 정렬과 삽입 정렬보다 성능이 훨씬 뛰어납니다.
이제 빠른 정렬이 어떻게 분할 정복을 이용하는지 알아보겠습니다. 병합 정렬에서 했던 것 처럼, 최초의 하위 배열이 array[0..n-1]인 하위 배열 array[p..r]을 정렬한다고 생각해 봅시다.
  1. 하위 배열 array[p.. r]에서 아무 요소를 골라 분할합니다. 이 요소를 피벗이라 합시다. array[p.. r] 안의 요소들을 재배열하여 array[p.. r] 안의 모든 요소 중 피벗보다 작거나 같은 요소는 피벗의 왼쪽으로 보내고, 나머지 요소는 모두 오른쪽으로 보냅니다. 이 과정을 파티션 하기라고 합니다. 이 과정에서, 피벗의 왼쪽과 오른쪽 요소들이 어떤 순서로 배열되는지는 상관없습니다. 중요한 것은 왼쪽과 오른쪽, 올바른 위치에 요소가 있어야 한다는 것입니다.
    일반적으로는 하위 배열에서 가장 오른쪽에 있는 요소 array[r]을 피벗으로 선택합니다. 예를 들어, 하위 배열이 [9, 7, 5, 11, 12, 2, 14, 3, 10, 6]으로 이루어져 있다면, 6을 피벗으로 선택해야 합니다. 파티션을 하고나면, 하위 배열은 [5, 2, 3, 6, 12, 7, 14, 9, 10, 11] 과 같이 될 것입니다. q는 나중에 피벗이 오는 자리를 나타냅니다.
  2. array[p..q-1] (피벗보다 작거나 같은, 즉 피벗의 왼쪽에 있는 모든 요소들)과 array[q+1..r] (피벗보다 큰, 즉 피벗의 오른쪽에 있는 모든 요소들)을 재귀적으로 정렬하여 정복합니다.
  3. 아무것도 하지 않으므로써 결합합니다. 정복 단계에서 한 번 재귀적으로 정렬했다면, 끝난 것입니다. 왜일까요? array[p..q-1]에 있는 피벗 왼쪽의 모든 요소는 피벗보다 작거나 같고, 정렬되었습니다. array[q+1..r]에 있는 피벗 오른쪽의 모든 요소는 피벗보다 크고, 정렬되었습니다. array[p..r]의 모든 요소는 정렬될 수 밖에 없습니다!
    예제를 대해서 생각해봅시다. 피벗 왼쪽과 오른쪽 하위 배열을 재귀적으로 정렬하면, 피벗 왼쪽의 하위 배열은 [2, 3, 5]이고, 피벗 오른쪽의 하위 배열은 [7, 9, 10, 11, 12, 14] 입니다. 따라서, 하위 배열은 [2, 3, 5] 다음 6, 그 다음 [7, 9, 10, 11, 12, 14]이 됩니다. 정렬이 끝난 것입니다.
탈출 조건은 병합 정렬에서와 같이 요소가 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 라이선스를 적용합니다.
로딩 중