지금까지 버블 정렬과 선택 정렬, 삽입 정렬 같은 많은 정렬 알고리즘을 살펴봤다. 하지만 실제로 배열을 정렬할 때는 이러한 방법을 쓰지 않는다. 컴퓨터 언어에는 대부분 내장 정렬 함수가 있어 사용자가 스스로 구현하는 데 드는 시간과 노력을 아껴준다. 컴퓨터 언어 중 대다수가 내부적으로 채택한 정렬 알고리즘이 바로 퀵 정렬이다.

퀵 정렬은 매우 빠른 정렬 알고리즘이다. 특히 평균 시나리오에서 효율적이다. 최악의 시나리오 즉, 역순으로 정렬된 배열에서는 삽입 정렬이나 선택 정렬과 성능이 유사하지만 대부분의 경우 일어나는 평균 시나리오에서는 훨씬 빠르다.

퀵 정렬의 동작 방식을 공부하면 재귀를 사용해 어떻게 알고리즘의 속도를 크게 향상시키는지 배울 수 있다.

13.1 분할

배열을 분할한다는 것은, 배열로부터 임의의 수를 가져와 피벗보다 작은 모든 수는 피벗의 왼족에, 피벗보다 큰 모든 수는 피벗의 오른쪽에 두는 것이다.

배열 [0, 5, 2, 1, 6, 3]에서, 3을 임의로 피벗으로 한다. 포인터 두 개를 사용해, 한 포인터는 배열의 첫 번째 원소(0)에, 다른 한 포인터는 피벗을 제외한 가장 오른쪽 원소(6)에 할당한다.

1. 왼쪽 포인터를 한 셀씩 계속 오른쪽으로 옮긴다. 피벗보다 크거나 같은 값에 도달하면 멈춘다.
2. 오른쪽 포인터를 한 셀씩 계속 왼쪽으로 옮긴다. 피벗보다 작거나 같은 값에 도달하면, 또는 배열의 맨 앞에 도달하면 멈춘다.
3. 오른쪽 포인터가 멈춘 후에는 둘 중 하나를 선택한다.
   1. 왼쪽 포인터가 오른쪽 포인터에 도달하거나 넘어섰을 경우 4단계로 넘어간다.
   2. 그렇지 않을 경우 왼쪽 포인터와 오른쪽 포인터가 가리키는 값을 교환한 후 1~3단계를 반복한다.
4. 끝으로 왼쪽 포인터가 현재 가리키고 있는 값을 피벗과 교환한다.

위의 배열([0, 5, 2, 1, 6, 3])을 예시로 직접 적용해보면 다음과 같다.

1. 왼쪽 포인터(0)와 피벗(3)을 비교한다. 피벗보다 작으므로 다음 단계에서 왼쪽 포인터를 옮긴다.
2. 왼쪽 포인터(5)와 피벗을 비교한다. 피벗보다 크므로 왼쪽 포인터 이동을 멈춘다.
3. 오른쪽 포인터(6)와 피벗을 비교한다. 피벗보다 크므로 다음 단계에서 오른쪽 포인터를 옮긴다.
4. 오른쪽 포인터 (1)와 피벗을 비교한다. 피벗보다 작으므로 오른쪽 포인터를 멈춘다.
5. 왼쪽 포인터(5)가 오른쪽 포인터에 도달하거나 넘어서지 않았으므로, 왼쪽 포인터와 오른쪽 포인터가 가리키는 값을 교환한다. [0, 1, 2, 5, 6, 3]다음 단계에서 왼쪽 포인터를 이동한다.
6. 왼쪽 포인터(2)와 피벗을 비교한다. 피벗보다 작으므로 다음 단계에서 왼쪽 포인터를 옮긴다.
7. 왼쪽 포인터(5)와 피벗을 비교한다. 피벗보다 크므로 왼쪽 포인터 이동을 멈춘다.왼쪽 포인터와 오른쪽 포인터가 같은 값을 가리키므로 포인터 이동을 중지한다.