퀵 정렬이란?

병합 정렬처럼 빠른 정렬도 분할 정복(divide-and-conquer) 전략을 사용하는 재귀 알고리즘입니다. 빠른 정렬에서 분할 정복 전략을 사용하는 방법은 병합 정렬에서 사용하는 방법과는 약간 다릅니다. 병합 정렬은 분할 단계에서 거의 아무 것도 하지 않고, 모든 중요한 작업은 결합 단계에서 일어납니다. 빠른 정렬은 반대인데, 모든 중요한 작업은 분할 단계에서 일어납니다. 사실 빠른 정렬은 결합 단계에서 정말 아무것도 하지 않습니다.

빠른 정렬은 병합 정렬과 다른 점이 몇 가지 있습니다. 빠른 정렬은 제자리에서 수행됩니다. 그리고 최악의 경우에 대한 수행 시간은 선택 정렬이나 삽입 정렬처럼 $\mathrm{\Theta }(n^2)$‍로 좋지 않습니다. 하지만 빠른 정렬의 평균 수행 시간은 병합 정렬만큼 좋은 $\mathrm{\Theta }(n{\log }_{2}n)$‍입니다. 병합 정렬과 비슷한 성능을 보이는데 빠른 정렬을 고려하는 이유는 무엇일까요? 그것은 big-Θ 표기법 속에 숨겨진 빠른 정렬의 상수항이 꽤 괜찮기 때문입니다. 실생활에서 빠른 정렬은 병합 정렬보다 성능이 좋으며, 선택 정렬과 삽입 정렬보다 성능이 훨씬 뛰어납니다.

이제 빠른 정렬이 어떻게 분할 정복을 이용하는지 알아보겠습니다. 병합 정렬에서 했던 것 처럼, 최초의 하위 배열이 array[0..n-1]인 하위 배열 array[p..r]을 정렬한다고 생각해 봅시다.

탈출 조건은 병합 정렬에서와 같이 요소가 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 라이선스를 적용합니다.