퀵소트의 핵심은 값을 한 번에 전부 정렬하는 데 있지 않고, 피벗의 최종 위치를 확정해 그 위치를 다시 건드리지 않는 데 있습니다. 각 분할 호출의 구간 경계와 불변식을 추적하면 피벗 선택이 시간과 재귀 깊이에 미치는 영향, 그리고 안정 정렬 여부를 같은 문제로 섞지 않고 판단할 수 있습니다.
분할 정복과 피벗 선택 원리
퀵소트는 피벗을 기준으로 작은 값과 큰 값을 나누고, 나뉜 구간을 다시 정렬하는 분할 정복 알고리즘입니다. 피벗 하나를 잘 선택하면 전체를 한 번 훑은 뒤 문제 크기를 거의 절반으로 줄일 수 있습니다. 반대로 매번 최솟값이나 최댓값을 고르면 한쪽에 거의 모든 원소가 남습니다.
다음 설명은 배열과 일관된 전순서 비교를 가정합니다. NaN이나 비교 도중 바뀌는 키가 있으면 먼저 비교 정책을 정해야 합니다. 여기서는 이해하기 쉬운 Lomuto partition을 사용합니다. 다른 분할 방식의 반환값과 재귀 경계를 섞으면 안 됩니다.
Lomuto partition 불변식과 피벗 위치 보장
배열의 닫힌 구간 [lo, hi]를 처리하고 마지막 원소를 피벗으로 고릅니다. 검사 위치 j 앞에서 다음 불변식을 유지합니다.
[lo, i)는 피벗 이하입니다.[i, j)는 피벗보다 큽니다.[j, hi)는 아직 검사하지 않았습니다.a[hi]는 피벗입니다.
a[j] <= pivot이면 a[i]와 교환하고 i를 증가시킵니다. 검사한 원소가 모두 처리되면 피벗을 i에 놓습니다. 이때 피벗은 최종 정렬 위치에 있으며 왼쪽과 오른쪽만 재귀 정렬하면 됩니다. 양쪽 부분 배열은 아직 정렬되지 않았다는 점이 중요합니다.
슈도코드
partition(a, lo, hi): // 닫힌 구간
pivot = a[hi]
i = lo
for j = lo .. hi - 1:
if a[j] <= pivot:
swap(a[i], a[j])
i = i + 1
swap(a[i], a[hi])
return i
quicksort(a, lo, hi):
if lo >= hi:
return
p = partition(a, lo, hi)
quicksort(a, lo, p - 1)
quicksort(a, p + 1, hi)
// 전체 배열: quicksort(a, 0, length(a) - 1)
피벗이 확정됐으므로 다음 호출에 p를 다시 포함하지 않습니다. 이 코드의 p는 Hoare partition의 구간 경계와 다릅니다. Hoare 방식의 재귀 범위를 여기에 복사하면 무한 반복이나 누락이 생길 수 있습니다.
Lomuto partition 단계별 추적
[4, 2, 5, 1, 3]에서 피벗은 3입니다.
| 검사 값 | 처리 뒤 배열 | i |
|---|---|---|
| 4 | [4, 2, 5, 1, 3] — 큰 구간에 남김 |
0 |
| 2 | [2, 4, 5, 1, 3] — 작은 구간으로 교환 |
1 |
| 5 | [2, 4, 5, 1, 3] |
1 |
| 1 | [2, 1, 5, 4, 3] |
2 |
| 피벗 배치 | [2, 1, 3, 4, 5] |
2 |
이제 3은 확정됐지만 왼쪽 [2, 1]은 아직 정렬해야 합니다. 최종 결과가 우연히 대부분 정렬되어 보인다고 분할만으로 전체 정렬이 끝난 것은 아닙니다.
그림을 글로 읽기
- 4 · 2 · 5 · 1 · 3: 닫힌 구간 [0, 4] · 마지막 값 3을 피벗으로 선택
- 2 · 1 │ 3 │ 4 · 5: 분할 반환값 p = 2 · 작은 구간은 아직 미정렬
- 2 · 1: quicksort(a, 0, 1)
- 4 · 5: quicksort(a, 3, 4)
- 4 · 2 · 5 · 1 · 3 → 2 · 1 │ 3 │ 4 · 5: 한 번 훑기
- 2 · 1 │ 3 │ 4 · 5 → 2 · 1: p 왼쪽
- 2 · 1 │ 3 │ 4 · 5 → 4 · 5: p 오른쪽
그림의 맨 아래 두 구간은 서로 겹치지 않습니다. 각 호출이 자기 구간을 정렬하면, 왼쪽 값은 모두 3 이하이고 오른쪽 값은 모두 3보다 크다는 분할 결과와 합쳐져 전체가 정렬됩니다. 별도로 두 구간을 병합할 필요가 없는 이유도 여기에 있습니다.
복잡도와 퇴화
분할 한 번은 길이 n에 대해 O(n)입니다. 균형 분할이 반복되면 깊이가 O(log n)이어서 전체는 O(n log n)입니다. 매번 0 : n-1로 갈리면 n + (n-1) + …의 일을 하므로 O(n²)이 됩니다.
이 슈도코드는 정렬된 입력과 모든 값이 같은 입력에서 특히 불균형해질 수 있습니다. 마지막 피벗을 쓰고 <=로 같은 값을 전부 왼쪽에 보내기 때문입니다. 기본 재귀 스택도 최악 O(n)이 됩니다. 제자리 분할이라는 말이 보조 공간을 전혀 사용하지 않는다는 뜻은 아닙니다.
같은 코드로 [1,2,3,4,5]를 처리하면 마지막 피벗 5가 매번 오른쪽 끝에 놓여 부분 문제 크기가 4, 3, 2, 1로 줄어듭니다. 모두 같은 값 [7,7,7,7,7]에서도 <= 조건 때문에 피벗이 끝으로 이동하는 같은 패턴이 나옵니다. 반대로 3-way partition은 동등 구간을 한 번에 확정해야 하므로 중복 입력에서 재귀 호출 수가 줄어드는지 별도로 세어야 합니다.
최악 시간·재귀 깊이와 안정성 보완 전략
- 무작위 피벗: 특정 입력 순서에 고정 피벗이 반복해서 실패하는 일을 확률적으로 줄입니다. 최악 입력 가능성을 없애는 절대 보장은 아닙니다.
- 3-way partition:
< pivot,== pivot,> pivot의 세 구간을 만듭니다. 동등 구간을 다시 정렬하지 않아 중복값이 많은 입력에 유리합니다. - 작은 구간 재귀, 큰 구간 반복: 재귀 스택을 O(log n) 수준으로 제한할 수 있지만 분할 자체의 O(n²) 시간은 여전히 남을 수 있습니다.
- introsort: 깊이 기준을 넘으면 heapsort로 전환해 최악 시간 상한을 확보하는 전략입니다. 작은 구간에서는 삽입 정렬을 사용할 수 있습니다.
이동·교환 과정에서 비교 키가 같은 원소의 입력 순서가 바뀔 수 있으므로 일반적인 제자리 퀵소트는 안정 정렬이 아닙니다. 안정성이 필요한 레코드는 라이브러리의 계약을 확인하거나 안정 정렬을 선택합니다.
입력 유형별 정렬·안정성 검증
- 빈 배열, 한 원소, 정렬·역정렬, 모두 같은 값, 중복이 많은 입력을 정렬합니다.
- 결과가 오름차순인지와 입력의 다중집합을 보존하는지를 따로 검사합니다.
- 비교 횟수와 최대 재귀 깊이를 기록해 최악 입력의 증가율을 봅니다.
- 값이 같은 레코드에 원래 순번을 붙여 안정성이 유지되는지 확인합니다.
퀵소트 시간 복잡도·분할 경계·안정성 요약
앞의 배열을 다시 손으로 확인할 때는 피벗이 어디에 놓였는지와 그 위치를 다음 호출에서 제외했는지를 먼저 봅니다. 그 뒤 한 층의 분할이 선형으로 끝나는지, 양쪽 크기가 어떻게 달라지는지에 따라 평균적인 O(n log n)과 최악의 O(n²)을 구분합니다. 무작위 피벗은 나쁜 입력을 만날 가능성을 낮출 뿐 최악 상한을 없애지 않으며, 상한이 필요하면 introsort처럼 다른 정렬로 전환하는 계약을 선택해야 합니다. 동점 레코드의 순서와 재귀 스택은 이 시간 계산과 별도로 확인합니다.
참고 자료
참고 링크는 추가 학습 경로입니다. 위 슈도코드는 원리를 설명하기 위한 별도 구현이며 특정 표준 라이브러리의 내부 구현을 그대로 나타내지 않습니다.