요약
- Quick Sort의 O(log N) 공간 복잡도는 재귀 호출 스택에서 발생한다
- in-place 정렬이라 추가 배열이 필요 없지만, 피봇 선택에 따라 최악의 경우 O(N)이 될 수 있다
본문
공간 복잡도의 원인: 재귀 콜 스택
Quick Sort는 in-place 정렬 알고리즘이다. 피봇을 기준으로 작은 값을 왼쪽에, 큰 값을 오른쪽에 배치하는 파티션 과정이 원본 배열 내에서 수행되므로 추가 배열이 필요 없다.
그러나 재귀적으로 왼쪽/오른쪽 부분 배열을 정렬할 때, 각 재귀 호출이 콜 스택에 쌓인다. 이 콜 스택의 깊이가 곧 공간 복잡도가 된다.
평균 O(log N) vs 최악 O(N)
- 평균적인 경우: 피봇이 배열을 대략 절반씩 나누면 재귀 깊이는 log N이 된다
- 최악의 경우: 이미 정렬된 배열에서 첫 번째나 마지막 원소를 피봇으로 선택하면, 한쪽은 0개, 다른 쪽은 N-1개가 되어 재귀 깊이가 N이 된다
따라서 "O(log N) 공간 복잡도"는 평균적인 경우이며, 최악의 경우 O(N)까지 증가할 수 있다.
Merge Sort와의 비교
Merge Sort도 재귀적 분할 정복이지만 공간 복잡도는 O(N)이다.
| Quick Sort | Merge Sort | |
|---|---|---|
| 파티션 방식 | in-place | 임시 배열 필요 |
| 추가 공간 | 콜 스택만 | 콜 스택 + 임시 배열 |
| 공간 복잡도 | O(log N) 평균 | O(N) |
Merge Sort는 정렬된 두 부분 배열을 합칠 때(merge) 임시 배열이 필요하고, 이 크기가 최대 N이 되기 때문이다.
최적화: Tail Recursion Elimination
최악의 경우에도 O(log N) 스택을 보장하는 방법이 있다:
- 두 파티션 중 작은 쪽을 먼저 재귀 호출
- 큰 쪽은 반복문(while)으로 처리
이렇게 하면 항상 작은 쪽만 스택에 쌓이므로 최악의 경우에도 log N 깊이가 보장된다.