(오름차순 기준)
→ 이 동작을 재귀 호출하여 퀵 정렬 구현
void quick(int a[], int left, int right)
{
int pl = left; /* 왼쪽 커서 */
int pr = right; /* 오른쪽 커서 */
int x = a[(pl + pr) / 2]; /* 피벗은 가운데 요소를 선택합니다. */
do {
while (a[pl] < x) pl++;
while (a[pr] > x) pr--;
if (pl <= pr) {
swap(a[pl], a[pr]);
pl++;
pr--;
}
} while (pl <= pr);
if (left < pr) quick(a, left, pr);
if (pl < right) quick(a, pl, right);
}
피벗을 선택하는 방법은 퀵 정렬의 실행 효율에 큰 영향을 줌
피벗 선택의 한 가지 방법
→ 이 방법은 나눌 그룹의 크기가 한쪽으로 치우치는 것을 피하면서도 나눌 때 스캔할 요소를 3개씩 줄일 수 있다는 장점이 있음