퀵 정렬

퀵 정렬은 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬 알고리즘이다. 분할 정복 기법을 사용하여 문제를 더 작은 단위로 쪼개어 해결한다. 대부분의 실질적인 데이터를 정렬할 때 다른 $O(n \log n)$ 알고리즘보다 빠르게 동작하는 경우가 많아 '퀵(Quick)'이라는 이름이 붙었다. 이는 내부 루프가 메모리 참조의 지역성을 높여 CPU 캐시 히트율이 높게 설계되었기 때문이다. 또한 매 단계에서 적어도 하나의 원소가 자기 자리를 찾게 되므로 이후 정렬할 대상이 줄어드는 특성이 있다.

퀵 정렬은 다음과 같은 단계로 진행된다.

1. 피벗 선택: 배열에서 하나의 원소를 피벗(Pivot)으로 선택한다.
2. 분할(Partitioning): 피벗을 기준으로 피벗보다 작은 원소들은 왼쪽으로, 큰 원소들은 오른쪽으로 재배치한다. 이 과정이 끝나면 피벗은 최종적으로 정렬된 위치에 고정된다.
3. 재귀적 정렬: 피벗을 제외한 왼쪽 부분 배열과 오른쪽 부분 배열에 대해 위 과정을 재귀적으로 반복한다.
4. 기저 조건: 부분 배열의 크기가 0 또는 1이 되면 정렬이 완료된 것으로 간주하고 재귀를 종료한다.

분할 후 병합 과정이 따로 필요하지 않으며, 제자리에서 데이터 교환을 통해 정렬이 이루어진다.

피벗 선택은 퀵 정렬의 성능에 결정적인 영향을 미친다. 부적절한 피벗 선택은 분할의 불균형을 초래하여 성능을 저하시킬 수 있다.

• 첫 번째 또는 마지막 원소: 구현이 간단하지만, 이미 정렬된 배열이나 역순으로 정렬된 배열에서 최악의 성능을 보인다.
• 무작위 선택(Random Pivot): 배열 내에서 임의의 원소를 피벗으로 선택하여 최악의 경우가 발생할 확률을 통계적으로 낮춘다.
• 세 값의 중앙값(Median-of-Three): 배열의 첫 번째, 중간, 마지막 원소 중 중앙값을 피벗으로 선택하여 보다 균형 잡힌 분할을 유도한다.

시간 복잡도

• 최선 및 평균: 리스트가 매번 균등하게 절반으로 나뉘는 경우 $O(n \log n)$의 비교를 수행한다.
• 최악: 피벗이 항상 리스트의 최솟값이나 최댓값으로 선택되어 분할이 극도로 불균형하게 일어나는 경우 $O(n^2)$의 비교를 수행한다.

공간 복잡도

퀵 정렬은 별도의 추가 배열을 생성하지 않고 원본 배열 내에서 위치를 바꾸는 제자리 정렬(In-place sort) 방식으로 구현이 가능하다. 다만 재귀 호출로 인해 발생하는 스택 공간이 필요하며, 평균적으로 $O(\log n)$, 최악의 경우 $O(n)$의 공간을 사용한다.

퀵 정렬은 동일한 값을 가진 원소들의 상대적인 순서가 정렬 후에 바뀔 수 있는 **불안정 정렬(Unstable Sort)**에 속한다. 예를 들어 동일한 값 5가 두 개 있을 때, 정렬 전후의 선후 관계가 유지되지 않을 수 있다.

또한 병합 정렬과 달리 리스트를 항상 균등하게 분할하는 것을 보장하지 않으므로 데이터의 분포에 따라 성능 편차가 발생할 수 있다. 그러나 대부분의 실제 데이터 세트에서 매우 효율적으로 동작하며, 참조 지역성(Locality of reference) 원리에 따른 캐시 친화적인 특성 덕분에 범용 정렬 알고리즘으로 널리 채택된다.