7 Quicksort

quicksort 알고리즘은 n개의 input array에 대해 최악의 경우 O(n^2)의 running time을 갖는다. 이 느린 worst-case running time에도 불구하고, quicksort는 정렬에 대해 가장 실용적인 선택인데, 왜냐하면 그것은 놀랍게도 평균에 대해 효율적이기 때문이다: 그것의 예상된 작동 시간은 O(n lgn)이고, 그 O(n lgn)에 숨겨진 상수 요소들은 꽤 작다. 그것은 또한 제자리에 정렬되는 장점을 가진다. 그리고 그것은 virtual-memory environments에서도 잘 작동한다.

Section 7.1은 그 알고리즘을 설명하고, partitioning을 위해 quicksort에 의해 사용된 중요한 subroutine을 설명한다. quicksort의 행동은 복잡하기 때문에, 우리는 Section 7.2에서 그것의 성능에 대해 직관적인 이야기로 시작하여, 그것의 정확한 분석을 챕터의 끝으로 지연시킨다. 이 알고리즘은 좋은 예상되는 작동 시간을 갖고, 어떠한 특정한 입력도 그것의 worst-case 행동을 이끌어 내지 않는다. Section 7.4는 그 randomized algorithm을 분석하고, 그것이 최악의 경우에 O(n^2) 에 작동한다는 것을 보여준다. 그리고 이것은 별개의 원소들에 대해서 O(nlgn) 시간에 예상된다.

7.1 Description of quicksort
merge sort처럼, Quicksort는 divide-and-conquer 패러다임을 적용한다. 여기에서 일반적인 subarray A[p..r]을 정렬하기 위한 세 단계의 divide-and-conquer process가 있다:

Divide: 그 array A[p.. r]를 두 개의 (가능한 텅 빈) subarrays A[p.. q - 1] 과 A[q + 1..r]로 나누는데, A[p.. q-1]의 각 원소가 A[q]보다 같거나 작게 하고, 차례대로 A[q+1..r]의 각 원소가 그것보다 같거나 크게 해라. 그 index q는 이 partitioning procedure의 일부로 연산해라.

Conquer: 두 subarrays A[p..q-1]과 A[q+1..r]를 quicksort에 대한 재귀호출로 정렬해라.

Combine: subarrays가 이미 정렬되었기 때문에, 그것들을 합칠 작업이 필요없다: 그 전체 배열 A[p..r]은 이제 정렬된다.

다음의 procedure는 quicksort를 구현한다:

QUICKSORT(A, p, r)
1 if p < r
2      q = PARTITION(A, p, r)
3      QUICKSORT(A, p, q - 1)
4      QUICKSORT(A, q + 1, r)

전체 행렬 A를 정렬하기 위해서, 그 초기 호출은 QUICKSORT(A, 1, A.length) 이다.

Partitioning the array
그 알고리즘에 대한 key는 PARTITION procedure인데, 그것은 subarray A[p..r]를 배치한다.

PARTITION(A, p, r)
1  x = A[r]
2  i = p - 1
3  for j = p to r - 1
4        if A[j] <= x
5            i = i + 1
6            exchange A[i] with A[j]
7  exchange A[i + 1] with A[r]
8  return i + 1

PARTITION은 항상 x = A[r]인 원소를 pivot element로 고르는데,  그걸로 subarray A[p..r]를 partition한다. procedure가 진행할 때, 그것은 그 array를 네 개의 구역으로 나눈다. lines 3-6에서 for loop의 매 반복의 ㅅ작에서, 그 영역은 어떤 특성을 만족한다.