quick sort — 최악 O(n²)인데 평균은 왜 O(n log n)인가

quick sort는 최악의 경우 $O(n^2)$까지 느려진다. 그런데도 현장에서 가장 널리 쓰이는 정렬이다. 모순처럼 보이는 이 사실의 답은 “평균”에 있다. 그 평균이 정말 $O(n \log n)$인지, 기댓값 점화식을 세워 끝까지 풀어 본다.

정렬 알고리즘 포스트에서 quick sort의 분할·올바름 증명·복잡도의 개요를 다뤘다. 그 글은 “평균은 왜 $O(n \log n)$인가”를 “한쪽으로 너무 쏠리지만 않으면 깊이가 로그” 라는 직관으로만 짚고 넘어갔다. 이 글은 그 빈칸을 채운다. 평균이 $\Theta(n \log n)$임을 수식으로 유도하는 것이 목표다.

---

분할 정복이지만, 절반을 보장하지 않는다

quick sort는 분할 정복이다. 하지만 merge sort가 배열을 정확히 절반으로 자르는 것과 달리, quick sort는 pivot이라 부르는 한 원소를 기준으로 “작은 것은 왼쪽, 큰 것은 오른쪽”으로 나눈다. 이 분할이 절반에 가까울지, 한쪽으로 쏠릴지는 입력과 pivot 선택에 달려 있다. 바로 이 점이 quick sort의 복잡도가 입력마다 달라지는 이유이고, 평균을 따져야만 하는 이유다.

먼저 분할이 어떻게 일어나는지부터 본다.

두 포인터로 한 배열 안에서 분할하기

가장 왼쪽 값 $a[0]$을 pivot $p$로 잡고, 두 포인터로 배열을 한 번 훑으며 제자리에서 분할한다.

void sort(int a[], int n) {
    if (n <= 1) return;     // 기저 사례: 크기 0·1은 이미 정렬됨
    int p = a[0];           // pivot: 맨 왼쪽 값
    int i = 1;              // 왼쪽 → 오른쪽으로 다가가는 포인터
    int j = n - 1;          // 오른쪽 → 왼쪽으로 다가가는 포인터
    while (i <= j) {
        while (i <= j && a[i] < p) i++;   // p보다 작은 동안 전진 → p 이상에서 멈춤
        while (i <= j && a[j] >= p) j--;  // p 이상인 동안 후진 → p 미만에서 멈춤
        if (i < j) swap(a[i], a[j]);      // 엇갈리기 전이면 두 값을 교환
    }
    swap(a[0], a[j]);       // pivot을 경계 j(항상 a[j] < p, 또는 j==0)로 → 최종 위치
    sort(a, j);             // 왼쪽 영역 재귀 (크기 j)
    sort(a + j + 1, n - j - 1);  // 오른쪽 영역 재귀 (크기 n−j−1)
}

과정

1. 맨 왼쪽의 값을 $p$(pivot)으로 잡는다.
2. 왼쪽에서 오른쪽으로 다가가는 포인터를 $i$, 오른쪽에서 왼쪽으로 다가가는 포인터를 $j$라 하자.
3. $i$는 $p$ 이상인 값($p_i$)을 만날 때까지 전진한다. $j$는 $p$보다 작은 값($p_j$)을 만날 때까지 후진한다.
4. $p_i \ge p$이고 $p_j < p$이므로, $p_i$와 $p_j$를 맞바꾸면 둘 다 제 영역으로 들어간다. 그러면 $i$와 $j$는 다시 전진·후진을 이어 갈 수 있다.
5. $i$와 $j$가 서로를 가로질러 엇갈리면 배열은 이렇게 정리되어 있다. 경계의 왼쪽에는 $p$보다 작은 값들만, 오른쪽에는 $p$ 이상인 값들만 남는다. pivot과 같은 값은 오른쪽에 모인다.
6. 따라서 마지막에 $p$(즉 $a[0]$)를 경계 자리 $a[j]$와 바꾸면, $p$를 기준으로 왼쪽엔 작은 값, 오른쪽엔 $p$ 이상인 값만 놓인다. 이 순간 $p$의 자리는 정렬이 끝난 뒤의 자리와 같다. 즉 최종 위치다.
7. 남은 일은 왼쪽 영역과 오른쪽 영역을 각각 재귀로 정렬하는 것뿐이다.

두 내부 조건이 한쪽은 a[i] < p, 다른 쪽은 a[j] >= p로 비대칭인 점에 주목하자. pivot과 같은 값($= p$)이 여러 개 있어도, $j$가 그런 값을 건너뛰며 후진하므로 포인터가 항상 한 칸 이상 진행한다. 덕분에 [5, 5]처럼 같은 값만 있는 입력에서도 멈추지 않고 정확히 정렬된다. 다만 정확히 정렬된다는 것과 빠르다는 것은 다른 이야기다. 같은 값만 있는 입력의 비용은 아래 평균 분석에서 다시 본다.

정렬 알고리즘 포스트의 분할은 경계 인덱스 하나(s)로 작은 값을 앞으로 모으는 방식이었다. 여기 두 포인터 방식은 같은 결과(작은 값 왼쪽 · $p$ 이상 오른쪽 · pivot은 최종 위치)를 양 끝에서 좁혀 오며 만든다. 분할의 결과는 같고 경로가 다를 뿐이다.

배열 2개를 쓰는 더 단순한 방법

위 방법은 배열 하나 안에서 끝내려다 보니 두 포인터를 엇갈리게 다루는 과정이 다소 복잡해 보인다. 배열을 두 개 쓰면 $i$, $j$를 둘 필요가 없다.

원본을 앞에서부터 훑으며, $p$보다 작은 값은 새 배열의 왼쪽 끝부터 차곡차곡 채우고, 큰 값은 오른쪽 끝부터 채운다. 다 훑고 나면 가운데 빈 한 칸에 $p$를 넣으면 된다. 포인터를 엇갈리게 관리할 필요 없이, 한 번의 패스로 분할이 끝난다.

대신 길이 $n$짜리 배열을 하나 더 쓰므로 추가 메모리 $O(n)$ 이 든다. 이는 merge sort가 떠안는 메모리 비용과 같은 종류의 트레이드오프다. quick sort가 실측에서 빠른 큰 이유 중 하나가 제자리(in-place) 분할이라는 점을 생각하면, 두 배열 방식은 이해를 돕는 설명용에 가깝다.

---

시간 문제: pivot이 어디에 놓이는가

분할 자체는 배열을 한 번 훑으므로 $O(n)$이다. 전체 복잡도는 pivot이 분할 후 어디에 놓이느냐, 즉 양쪽 영역의 크기가 어떻게 갈리느냐에 전적으로 달려 있다.

• 정확히 반으로 나뉠 때(최선). pivot이 매번 중앙값이면 $T(n) = 2T(n/2) + n$이 되어, merge sort와 같은 $O(n \log n)$이다.
• 한쪽으로 완전히 쏠릴 때(최악). pivot이 매번 최솟값이나 최댓값이면 한쪽은 $0$개, 다른 쪽은 $n-1$개가 된다. $T(n) = T(n-1) + n$이 되어 $O(n^2)$로 추락한다. 이미 정렬된(또는 역순으로 정렬된) 배열에 항상 $a[0]$을 pivot으로 잡으면 정확히 이 최악 경우다.

$O(n \log n)$과 $O(n^2)$의 간극은 거대하다. 그렇다면 “보통” 입력에서는 어느 쪽에 가까울까? 이 질문에 답하려면 평균을 정의해야 한다.

---

평균은 왜 $O(n \log n)$인가

평균을 말하려면 확률을 가정해야 한다

“평균”은 입력의 확률분포가 주어져야만 말할 수 있는 개념이다. 분포가 없으면 평균도 없다. 아래 분석이 세우는 모형은 이것이다.

분석의 무기는 기댓값의 선형성이다. 어떤 두 양 $A$, $B$에 대해서도 다음이 성립한다.

$$E(A + B) = E(A) + E(B)$$

이 성질 덕분에, 복잡하게 얽힌 비용도 조각조각 나눠 기댓값을 더할 수 있다.

기댓값 점화식 세우기

$n$개를 정렬하는 데 드는 시간의 기댓값을 $E(n)$이라 하자. pivot의 ‘등수’를 $k$라 하면, 분할 후 왼쪽에는 $k-1$개, 오른쪽에는 $n-k$개가 남는다.

pivot 등수 $k$	왼쪽 크기	오른쪽 크기
$1$	$0$	$n-1$
$2$	$1$	$n-2$
$3$	$2$	$n-3$
$\vdots$	$\vdots$	$\vdots$
$n$	$n-1$	$0$

각 등수 $k$가 확률 $\frac{1}{n}$로 나오고, 그때 두 부분문제의 비용은 $E(k-1)$과 $E(n-k)$다. 여기에 분할 자체의 비용 $n$($i$, $j$가 배열 전체를 훑는 시간)을 더하면, 기댓값의 선형성으로 다음 점화식이 선다.

$$E(n) = \sum_{k=1}^n \frac{E(k-1) + E(n-k)}{n} + n$$

점화식을 풀어 나가기

합을 펼쳐 쓰면, $k$가 $1$에서 $n$까지 돌 때 $E(0), E(1), \ldots, E(n-1)$이 각각 두 번씩 나타난다.

$$E(n) = \frac{\{E(0) + E(n-1)\} + \{E(1) + E(n-2)\} + \cdots + \{E(n-1) + E(0)\}}{n} + n$$

같은 항이 두 번씩이므로 묶으면,

$$E(n) = \frac{2}{n} \sum_{k=0}^{n-1} E(k) + n$$

양변에 $n$을 곱해 합 기호를 다루기 쉽게 만든다.

$$n \cdot E(n) = 2\sum_{k=0}^{n-1} E(k) + n^2$$

이제 같은 식을 $n$ 대신 $n-1$에 대해 써 보자.

$$(n-1)\cdot E(n-1) = 2\sum_{k=0}^{n-2} E(k) + (n-1)^2$$

두 식을 빼면 합 기호가 $E(n-1)$ 한 항만 남기고 사라진다.

$$n E(n) - (n-1)E(n-1) = 2E(n-1) + n^2 - (n-1)^2 = 2E(n-1) + 2n - 1$$

$(n-1)E(n-1)$을 우변으로 넘겨 정리하면, 깔끔한 1차 점화식이 된다.

$$n \cdot E(n) = (n+1)\cdot E(n-1) + 2n - 1$$

텔레스코핑으로 닫힌 식에 다가가기

양변을 $n(n+1)$로 나누면, $\frac{E(n)}{n+1}$과 $\frac{E(n-1)}{n}$이 같은 꼴로 나란히 놓인다.

$$\frac{E(n)}{n+1} = \frac{E(n-1)}{n} + \frac{2n - 1}{n(n+1)} = \frac{E(n-1)}{n} + \frac{3}{n+1} - \frac{1}{n}$$

마지막 등호는 $\frac{2n-1}{n(n+1)}$을 부분분수로 쪼갠 것이다($-\frac{1}{n} + \frac{3}{n+1}$). 이제 $F(n) = \dfrac{E(n)}{n+1}$로 두면 식은 한 칸씩 더해 나가는 모양이 된다.

$$F(n) = F(n-1) + \left(\frac{3}{n+1} - \frac{1}{n}\right)$$

$F(n-1)$을 다시 $F(n-2)$로, 그 다음을 또 그 앞으로 바꾸어 바닥까지 펼치면(텔레스코핑) 추가항들이 전부 더해진다.

$$\frac{3}{2} - \frac{1}{1} + \frac{3}{3} - \frac{1}{2} + \frac{3}{4} - \frac{1}{3} + \frac{3}{5} - \frac{1}{4} + \cdots$$

같은 분모끼리 다시 묶으면 정리된다(유한합이라 실제로는 꼬리항 $\frac{3}{n+1}$과 초기값 $F(0)$가 남지만, 둘 다 상수·저차항이라 점근 분석에서 무시한다. 그래서 아래 등호는 지배항만 남긴 근사다).

$$= -\frac{1}{1} + \left(\frac{3}{2} - \frac{1}{2}\right) + \left(\frac{3}{3} - \frac{1}{3}\right) + \left(\frac{3}{4} - \frac{1}{4}\right) + \cdots = -3 + 2\left(\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \cdots\right)$$

여기서 괄호 안은 조화수(harmonic number) $H_n = \sum_{k=1}^{n} \frac{1}{k}$이고, 잘 알려진 대로 $H_n \approx \ln n$이다(자연로그가 나오는 이유는 $\frac{1}{k}$의 합이 $\int \frac{1}{x}\,dx = \ln x$에 대응하기 때문이다). 따라서 추가항들의 총합은 약 $2\ln n - 3$이고, 텔레스코핑의 결과로 $F(n)$ 자체가 이 값에 닿는다.

$$\frac{E(n)}{n+1} \approx 2\ln n - 3$$

결론: 평균은 $\Theta(n \log n)$

$\frac{E(n)}{n+1} \approx 2\ln n$이므로 양변에 $(n+1)$을 곱하면 $E(n) \approx 2(n+1)\ln n$이다. 자연로그 $\ln n$과 임의 밑의 $\log n$은 상수배만큼만 다르므로($\ln n = \log_2 n \cdot \ln 2$), 점근적으로는 다음과 같이 쓴다.

$$E(n) \approx 2(n+1)\ln n = \Theta(n \log n)$$

최악이 $O(n^2)$인 알고리즘의 평균이 $O(n \log n)$이라는 결론이다. 직관으로도 들어맞는다. $O(n \log n)$과 $O(n^2)$의 간극이 워낙 크기 때문에, 최악의 쏠린 분할이 매 단계 반복되어야만 평균이 $O(n^2)$ 쪽으로 끌려간다. 그런데 무작위 입력에서 그런 극단이 매번 일어날 확률은 지극히 작아, 기대 깊이는 로그 규모에 머문다. 실험적으로 측정해 봐도 평균은 $O(n \log n)$으로 나타난다.