(오름차순 기준)

배열을 두 그룹으로 나누는 동작

  1. 무작위의 피벗 x 선택
  2. 왼쪽 끝 요소의 인덱스 pl(왼쪽 커서)
  3. 오른쪽 끝 요소의 인덱스 pr(오른쪽 커서)
  4. 요소의 교환
    1. a[pl] ≥ x가 성립하는 요소를 찾을 때까지 pl을 오른쪽으로 옮김
    2. a[pr] ≤ x가 성립하는 요소를 찾을 때까지 pr을 왼쪽으로 옮김
    3. 두 요소 교환

→ 이 동작을 재귀 호출하여 퀵 정렬 구현

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);
}

피벗 선택

시간 복잡도 : O(n log n)