퀵 정렬이란?
퀵 정렬(Quick Sort)은 기준값(피벗, pivot) 하나를 정하고, 그보다 작은 값은 왼쪽·큰 값은 오른쪽으로 나눈 뒤, 양쪽을 같은 방식으로 다시 정렬하는 분할 정복(divide and conquer) 알고리즘입니다. 병합 정렬과 함께 평균 O(n log n)을 대표하지만, 추가 메모리를 거의 쓰지 않고 제자리(in-place)에서 정렬한다는 점이 다릅니다.
핵심 한 줄: "피벗을 제자리에 갖다 놓는다." 한 번의 분할이 끝나면 피벗은 정렬이 끝났을 때의 최종 위치에 정확히 자리 잡습니다.
핵심은 분할(partition)
퀵 정렬의 거의 모든 일은 분할 단계에서 일어납니다.
1. 구간의 한 원소를 피벗으로 고릅니다(여기서는 마지막 값).
2. 구간을 훑으면서 피벗보다 작은 값들을 앞쪽으로 모읍니다.
3. 마지막에 피벗을 그 경계로 옮기면, 피벗 왼쪽은 전부 작고 오른쪽은 전부 크다는 상태가 됩니다.
이제 피벗은 더 건드릴 필요가 없습니다. 왼쪽 구간과 오른쪽 구간을 각각 독립적으로 같은 분할로 반복하면 전체가 정렬됩니다.
동작 원리
1단계. 정렬할 구간 [lo, hi]에서 pivot = arr[hi]로 둡니다.
2단계. 경계 인덱스 i = lo를 둡니다. j를 lo부터 hi-1까지 옮기며 arr[j] < pivot이면 arr[i]와 교환하고 i를 1 늘립니다.
3단계. 스캔이 끝나면 arr[i]와 arr[hi](피벗)를 교환합니다. 이제 피벗은 인덱스 i에 확정됩니다.
4단계. [lo, i-1]과 [i+1, hi]에 대해 1~3단계를 재귀로 반복합니다. 구간 크기가 1 이하면 멈춥니다.
"비교"와 "교환"은 서로 다른 동작입니다. 알고노트 시각화도 비교 단계와 교환 단계를 따로 보여줍니다.
시간복잡도와 공간복잡도
| 복잡도 | |
|---|---|
| 시간(평균) | O(n log n) |
| 시간(최악) | O(n²) |
| 공간 | O(log n) |
평균적으로 분할이 절반씩 일어나 깊이가 log n, 각 깊이에서 n번 비교하므로 O(n log n)입니다. 그러나 이미 정렬된 배열에서 항상 끝값을 피벗으로 잡으면 한쪽이 비어 깊이가 n까지 늘어나 O(n²)이 됩니다. 공간은 재귀 호출 스택만큼(O(log n))이고 별도의 큰 배열은 쓰지 않습니다.
예시로 따라가기
arr = [5, 2, 8, 1, 4]에서 피벗을 마지막 값 4로 잡습니다.
- •j=0: 5 < 4? 아니오
- •j=1: 2 < 4? 예 → arr[0]과 교환 →
[2, 5, 8, 1, 4], i=1 - •j=2: 8 < 4? 아니오
- •j=3: 1 < 4? 예 → arr[1]과 교환 →
[2, 1, 8, 5, 4], i=2 - •마지막에 arr[2]와 피벗 교환 →
[2, 1, 4, 5, 8]
피벗 4는 인덱스 2에 확정됐고, 왼쪽 [2, 1]과 오른쪽 [5, 8]을 다시 정렬하면 끝입니다.
자주 하는 실수
- •피벗 선택: 항상 끝값을 고르면 정렬된 입력에서 O(n²). 무작위 피벗이나 median-of-three로 완화합니다.
- •등호 처리:
arr[j] < pivot의 부등호를 잘못 쓰면 중복 값이 많을 때 분할이 한쪽으로 쏠려 성능이 나빠집니다. - •종료 조건:
lo < hi일 때만 분할해야 하며, 원소가 1개 이하인 구간은 이미 정렬된 상태입니다.
알고노트에서 직접 확인하세요
피벗이 어떻게 정해지고, 작은 값이 앞으로 모이며, 피벗이 제자리를 찾는 과정을 알고노트에서 단계별로 확인할 수 있습니다.