기준값(pivot) 하나를 골라 제자리로 보내고, 그보다 작은 것은 왼쪽 큰 것은 오른쪽으로 몰아 두 덩어리로 나눈 뒤 각각 같은 일을 반복하는 정렬. 합병 정렬과 마찬가지로 분할 정복인데, 나뉘는 크기가 균등하지 않다는 점이 다르다.
파티셔닝
파티셔닝이 피벗을 기준으로 좌우를 가르는 과정이다. 왼쪽 인덱스는 피벗보다 작은 값을 지나치며 오른쪽으로 가다가 피벗보다 큰 값을 만나면 멈춘다. 오른쪽 인덱스는 피벗보다 큰 값을 지나치며 왼쪽으로 가다가 피벗보다 작은 값을 만나면 멈춘다. 멈춘 두 값을 교환하고, 두 인덱스가 엇갈릴 때까지 반복한다. 끝나면 피벗을 기준으로 작은 것과 큰 것이 갈라져 있다.
복잡도와 콜 스택
최선과 평균은 O(n log n)이다. 공간복잡도는 O(log n)인데, 배열 자체는 교환만 하므로 제자리 정렬이고 재귀 호출 때문에 콜 스택이 트리 높이만큼 쌓이기 때문이다. 파티셔닝에서 멀리 떨어진 원소끼리 교환하므로 안정 정렬은 아니다.
최악이 O(n²)인 경우
최악이 O(n²)이다. 피벗으로 매번 최솟값이나 최댓값을 고르면 한쪽이 0개, 다른 쪽이 n-1개로 갈려서 깊이가 n이 된다. 확률적으로 희박하지만 정렬된 배열에서 첫 원소를 피벗으로 잡으면 반드시 일어나고, 이때 콜 스택도 O(n)까지 간다.
그래도 합병 정렬보다 빠른 이유
그런데도 실제로는 합병 정렬보다 빠르다. 평균적으로 퀵 정렬이 더 빠르고, 실전에서는 n log n보다도 빠르게 도는 경우가 많다. 상수가 작고 임시 배열을 안 만들기 때문이다.
피벗 고르기
피벗을 어떻게 고를지에는 정답이 없어서 아직도 논문이 나온다. 첫 원소는 가장 간단하지만 정렬된 입력에서 최악이 확정이고, 가운데 원소가 흔히 쓰는 절충안이며, 무작위로 고르면 최악이 나올 확률을 입력과 무관하게 만든다. 자바 표준 라이브러리가 쓰는 듀얼 피벗 방식은 안정 정렬에 적어두었다.