퀵 정렬(Quick Sort)의 매력: 기준점(Pivot) 하나로 정렬 끝내는 방법

프로그래밍 언어(C, C++, Java 등)의 내장 정렬 함수인 sort() 내부를 들여다보면, 높은 확률로 이 알고리즘이 탑재되어 있습니다. 이름부터 '나 졸라 빠름(Quick)'이라고 당당하게 선언하고 있는 알고리즘, 바로 '퀵 정렬(Quick Sort)'입니다. 병합 정렬처럼 분할 정복(Divide and Conquer) 방식을 사용하지만, 무식하게 반으로 쪼개는 것이 아니라 '기준점(Pivot)'이라는 영리한 카드를 내세워 평균적으로 병합 정렬보다 2~3배 더 빠른 미친 속도를 자랑합니다. 추가 메모리조차 거의 쓰지 않는 퀵 정렬의 치명적인 매력을 해부해 봅니다.

1. 피벗(Pivot): 내 기준으로 헤쳐 모여!

퀵 정렬은 배열에서 아무 원소나 하나 콕 집어 이를 피벗(Pivot, 기준점)이라고 부릅니다. 그리고 이 피벗을 기준으로 배열을 무자비하게 두 동강 냅니다.

• 왼쪽 파티: 피벗보다 작은 숫자들은 전부 내 왼쪽으로 가!
• 오른쪽 파티: 피벗보다 큰 숫자들은 전부 내 오른쪽으로 가!

이 과정을 파티션(Partition)이라고 부릅니다. 파티션이 한 번 끝나면, 왼쪽과 오른쪽이 정렬되었는지는 몰라도, 최소한 '피벗' 그 자신의 위치만큼은 전체 배열에서 완벽하게 확정(정렬 완료)됩니다. 이제 피벗을 제외하고 갈라진 왼쪽 그룹과 오른쪽 그룹에 대해 각각 새로운 피벗을 뽑아 파티션을 재귀적으로 반복하면 순식간에 정렬이 끝납니다.

2. 투 포인터를 이용한 스와핑 예술

파티션을 어떻게 추가 메모리 없이(In-place) 빠릿빠릿하게 해낼까요? 배열의 양 끝에 Low 포인터와 High 포인터를 둡니다.

1. Low 포인터는 왼쪽에서 오른쪽으로 이동하며 '피벗보다 큰 놈'을 찾습니다. (왼쪽엔 작은 놈만 있어야 하니까, 룰을 어긴 놈을 색출하는 겁니다.)
2. High 포인터는 오른쪽에서 왼쪽으로 이동하며 '피벗보다 작은 놈'을 찾습니다.
3. 둘 다 범인을 찾았다면, 두 녀석의 자리를 바꿉니다(Swap).
4. 이 과정을 Low와 High 포인터가 서로 엇갈릴 때까지 반복하고, 마지막에 엇갈린 위치에 피벗을 꽂아 넣습니다.

이 스와핑 메커니즘은 CPU의 캐시 메모리 적중률(Cache Locality)을 극한으로 끌어올리기 때문에, 동일한 O(N log N) 알고리즘들 사이에서도 퀵 정렬이 압도적으로 빠른 실제 실행 속도를 보여주는 비결이 됩니다.

3. 퀵 정렬의 치명적 약점: O(N^2)의 저주

하지만 퀵 정렬에도 지옥 같은 약점이 하나 있습니다. 만약 배열이 [1, 2, 3, 4, 5]처럼 이미 정렬되어 있는데, 하필 가장 작은 1을 피벗으로 계속 고른다면 어떻게 될까요?
분할이 절반씩 예쁘게 쪼개지지 않고, (0개) 피벗 (N-1개) 형태로 극단적으로 치우치게 됩니다. 이 짓을 N번 반복해야 하므로, 시간 복잡도는 O(N^2)으로 수직 낙하해 버립니다. 이 끔찍한 사태를 막기 위해 현대의 퀵 정렬 구현체들은 피벗을 랜덤하게 고르거나, 맨 앞, 중간, 맨 뒤의 3개 값 중 중간값(Median of Three)을 피벗으로 삼는 등 철저한 방어 기제를 겹겹이 두르고 있습니다.

[핵심 요약]
1. 퀵 정렬(Quick Sort)은 피벗(Pivot)을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할하며 정렬해 나가는 분할 정복 알고리즘입니다.
2. 추가 메모리를 거의 쓰지 않고(In-place) CPU 캐시 효율이 뛰어나, 평균적으로 O(N log N) 알고리즘 중 가장 빠르고 널리 쓰이는 실전형 정렬입니다.
3. 최악의 경우(피벗이 항상 최솟값이나 최댓값으로 쏠릴 때) O(N^2)으로 느려지는 단점이 있어, 피벗을 무작위나 중간값으로 잘 고르는 최적화가 필수적입니다.