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

pl과 pr이 교차하면 그룹을 나누는 과정이 끝나고 배열은 아래처럼 두 그룹으로 나누어집니다.

피벗 이하의 그룹 : a[0], … , a[pl – 1]
피벗 이상의 그룹 : a[pr + 1], … , a[n – 1]

또 그룹을 나누는 작업이 끝난 다음 pl  pr + 1인 경우에는 다음과 같은 그룹이 생길 수 있습

니다.

피벗과 일치하는 값을 가지는 그룹 : a[pr + 1], … , a[pl – 1]

앞의 예에서는 피벗과 일치하는 값을 가지는 그룹이 만들어지지 않았습니다. 그림 6-20은 피
벗과 일치하는 값을 가지는 그룹이 만들어지는 예입니다. a 는 초기 상태이고 피벗의 값은

5입니다.

pl pr
０ １ ２ ３ ４ ５ ６ ７ ８
a 1 8 7 4 5 2 6 3 9

pl pr
b 1 8 7 4 5 2 6 3 9

pl pr
c 1 3 7 4 5 2 6 8 9

pl
pr
d 1 3 2 4 5 7 6 8 9

pl
pr
e 1 3 2 4 5 7 6 8 9
피벗 이하
피벗 이상
피벗과 일치
왼쪽 그룹 가운데 그룹 오른쪽 그룹
[그림 6-20] 피벗과 같은 값을 가지는 그룹이 생긴 경우

b , c , d 는 왼쪽 커서, 오른쪽 커서가 피벗 이상, 피벗 이하의 요소를 찾아 멈춘 단계입니다.

그림 d 는 pl, pr이 동일한 요소 a[4] 위에 있습니다. 이때 동일한 요소인 a[4]와 a[4]를 교환합

226 C 알고리즘