퀵 정렬

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

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

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

시간 복잡도

• 평균 및 최선: $O(n \log n)$의 비교를 수행한다.
• 최악: 피벗이 항상 리스트의 최솟값이나 최댓값으로 선택되는 경우 $O(n^2)$의 비교를 수행한다. 그러나 실제 데이터에서 이러한 경우가 발생할 확률은 낮도록 설계가 가능하다.

공간 복잡도

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

퀵 정렬은 동일한 값을 가진 원소들의 상대적인 순서가 정렬 후에 바뀔 수 있는 **불안정 정렬(Unstable Sort)**에 속한다. 예를 들어 5(A), 5(B), 3, 2, 1을 정렬할 경우 1, 2, 3, 5(B), 5(A)와 같이 순서가 뒤바뀔 수 있다. 또한 병합 정렬과 달리 리스트를 균등하게 분할하는 것을 보장하지 않으므로, 피벗 선택 전략에 따라 성능 편차가 발생할 수 있다.