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

배열을 두 그룹으로 나누기

먼저 배열을 두 그룹으로 나누는 순서에 대해서 살펴보겠습니다. 다음의 배열에서 피벗으로
6을 선택하여 나눕니다. 피벗을 x, 왼쪽 끝 요소의 인덱스 pl을 왼쪽 커서, 오른쪽 끝 요소의
인덱스 pr을 오른쪽 커서라고 하겠습니다.

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

그룹을 나누려면 피벗 이하의 요소를 배열 왼쪽으로, 이상의 요소를 배열 오른쪽으로 옮겨야
합니다. 그렇게 하려면 아래의 작업을 먼저 수행해야 합니다.

1. a[pl] >= x가 성립하는 요소를 찾을 때까지 pl을 오른쪽으로 옮깁니다.
2. a[pr] <= x가 성립하는 요소를 찾을 때까지 pr을 왼쪽으로 옮깁니다.

이 과정을 거치면 pl과 pr은 아래 그림의 위치에서 멈추게 됩니다. pl이 위치한 지점은 피벗
값 이상의 요소가 있는 지점이고 pr이 위치한 지점은 피벗 값 이하의 요소가 있는 지점입니

다. 여기서 왼쪽(pl)과 오른쪽(pr) 커서가 가리키는 요소 a[pl]과 a[pr]의 값을 교환합니다. 그
러면 피벗 이하의 값은 왼쪽으로 이동하고 피벗 이상의 값은 오른쪽으로 이동합니다.

pl pr
5 7 1 4 6 2 3 9 8

다시 스캔을 진행하면 왼쪽과 오른쪽 커서는 아래 그림의 위치에서 멈춥니다. 다시 이 두 요
소 a[pl]과 a[pr]의 값을 교환합니다.

pl pr
5 3 1 4 6 2 7 9 8

다시 스캔을 계속하면 아래 그림처럼 두 커서(pl, pr)가 교차하게 됩니다.

pr pl
5 3 1 4 2 6 7 9 8

피벗 이하 피벗 이상

06•정렬 225