Page 240 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

피벗 선택하기

피벗을 선택하는 방법은 퀵 정렬의 실행 효율에 큰 영향을 줍니다. 이번에는 피벗 선택 방법
을 다음의 배열을 예로 들어 살펴보겠습니다.

8 7 6 5 4 3 2 1 0

피벗으로 왼쪽 끝 요소(8)를 선택합니다. 그러면 이 배열은 피벗의 값(8)만 있는 그룹과 나머

지 그룹으로 나누어집니다. 하나의 요소와 나머지 요소로 나누어지는(한쪽으로 치우친) 분할을
반복하는 방법으로는 빠른 정렬 속도를 기대할 수 없습니다. 빠른 정렬을 원한다면 배열을 정
렬한 다음에 가운데 값을 피벗으로 하면 됩니다. 배열의 크기가 균등하게 나누어지기 때문입
니다. 그러나 가운데 값을 구하고자 할 경우 그에 대한 처리가 필요하고 이 처리에 대해 많은

계산 시간이 요구되어 배보다 배꼽이 커집니다. 이런 문제를 해결하기 위해 다음의 방법을 사
용하면 적어도 최악의 경우는 피할 수 있습니다.

방법 1. 나눌 배열의 요소 개수가 3 이상이면 임의로 3 요소를 선택하고 그중에서 중앙값인 요소를 피벗으로
선택합니다.

예를 들어 위의 배열에서 첫 요소(8), 가운데 요소(4), 끝 요소(0) 중에서 한 요소를 선택해야 하
는 경우 중간 크기의 값(4)을 피벗으로 하면 최악으로 그룹이 나누어지는 경우는 피할 수 있습
니다.

이 아이디어를 조금 더 발전시킨 방법은 다음과 같습니다.

방법 2. 나눌 배열의 처음, 가운데, 끝 요소를 정렬한 다음 가운데 요소와 끝에서 두 번째 요소를 교환합니
다. 피벗으로 끝에서 두 번째 요소의 값(a[right – 1])을 선택하여 나눌 대상의 벙위를 a[left + 1] ~
a[right – 2]로 좁힙니다.

다음은 그림 6-27을 구체적으로 설명한 내용입니다.

a 정렬하기 전 상태입니다. 첫 요소(8), 가운데 요소(4), 끝 요소(0)를 선택하여 이 세 요소를 정렬합니다.
b 첫 요소는 0, 가운데 요소는 4, 끝 요소는 8이 되었습니다. 여기에서 가운데 요소(4)와 끝에서 두 번째 요
소(1)를 교환합니다.
c 끝에서 두 번째 요소(4)를 피벗으로 합니다. a[left]는 피벗 이하의 값이고 a[right – 1]과 a[right]는 피
벗 이상의 값입니다.

240 C 알고리즘