정렬 알고리즘 — Selection / Merge / Quick

정렬은 알고리즘 수업의 단골 주제다. 같은 문제를 푸는 세 가지 방식이 각각 어떤 가정을 깔고 있고, 왜 복잡도가 갈리는지 들여다본다.

정렬 문제의 두 조건

입력 배열을 $a[\,]$, 출력 배열을 $b[\,]$라 하자. “$b$는 $a$를 정렬한 결과”라는 말은 다음 두 조건을 동시에 만족한다는 뜻이다.

조건	의미
멀티셋 조건	$a$와 $b$에서 각 값의 등장 횟수가 같다 (중복까지 고려해 같은 원소 모음)
정렬 조건	$b[0] \le b[1] \le \cdots \le b[n-1]$ (비감소 순서)

멀티셋 조건은 “값이 생겨나거나 사라지지 않는다”는 뜻이다. 일반 집합과 달리 멀티셋으로 보는 이유는, 같은 값이 여러 번 나오는 입력에서도 그 개수가 보존되어야 하기 때문이다. 정렬 조건은 “비감소(오름차순, 같은 값 허용)“이다.

세 알고리즘이 멀티셋 조건을 보존하는 방식은 조금 다르다. selection sort와 quick sort는 제자리 교환(swap)만으로 원소를 재배치하므로 개수가 자동 보존되고, merge sort는 보조 배열에 모든 원소를 정확히 한 번씩 복사하므로 보존된다. 증명의 무게는 어느 쪽이든 정렬 조건에 실린다.

다만 아래 올바름 증명들은 표기를 단순하게 하기 위해 중복이 없는 입력(strict less-than) 을 가정한다. 같은 값이 있을 때는 $<$를 $\le$로 바꾸고, quick sort는 pivot과 같은 값의 처리 규칙(아래 partition 참고)을 더하면 논의가 그대로 확장된다.

---

Selection Sort

selection sort는 가장 직관적인 정렬이다. “남은 원소 중 가장 작은 것을 골라 앞으로 보낸다”를 끝까지 반복한다.

반복문 버전

void sort(int a[], int n) {
    for (int i = 0; i < n; i++) {
        // 1. a[i..n-1] 중 최솟값의 인덱스를 찾는다
        int m = i;
        for (int j = i; j < n; j++) {
            if (a[m] > a[j]) m = j;
        }
        // 2. 최솟값을 i번째 자리로 보낸다
        int t = a[i];
        a[i] = a[m];
        a[m] = t;
    }
}

정렬됨의 증명 — 루프 불변식

핵심 도구는 루프 불변식(Loop Invariant) 이다.

불변식 $I_k$: $k$번째 바깥쪽 루프가 끝난 직후,

1. $a[0] < a[1] < \cdots < a[k-1]$ (앞쪽이 정렬되어 있다)
2. 모든 $i < k$와 모든 $x \ge k$에 대해 $a[i] < a[x]$ (앞쪽 전체가 뒤쪽 전체보다 작다)

조건 2를 "$a[k-1] < a[x]$"로 줄여 쓰고 싶어지지만, 그러면 $k = 0$에서 존재하지 않는 $a[-1]$을 가리키게 된다. 정의되지 않은 항을 참조하는 명제는 참도 거짓도 아니다. 두 첨자를 모두 열어 두면 $k=0$에서 $i < 0$인 $i$가 없어 조건이 공허하게 참이 되고, 기저가 깨끗하게 닫힌다. 조건 1이 있으므로 $k \ge 1$에서는 두 형태가 같은 말이다. 아래 그림이 보여 주는 것도 그 경우다.

$n$번째 루프가 끝난 후, 조건 1에 의해 $a[0] < a[1] < \cdots < a[n-1]$이 성립한다. 조건 2는 $x \ge n$인 $x$가 없으므로 역시 공허하게 참이다. 따라서 불변식이 매 단계 유지되면 정렬이 완성된다.

위 그림에서 보듯 $k=3$ 시점에는 앞쪽 3칸이 정렬을 마쳤고, 뒤쪽 원소들은 모두 앞쪽의 마지막 값보다 크다. 작은 배열로 직접 따라가 보면 더 분명하다. [3, 1, 2]를 정렬하면:

• $i=0$: 최솟값 1을 맨 앞으로 → [1, 3, 2]
• $i=1$: 남은 [3, 2]의 최솟값 2를 → [1, 2, 3]
• $i=2$: 남은 원소가 하나뿐 → [1, 2, 3] 완료

매 단계 앞쪽이 한 칸씩 확정되는 것이 불변식 그대로다.

불변식의 귀납적 증명:

• 기초 ($k = 0$): 조건 1은 비교할 쌍이 없고, 조건 2는 $i < 0$인 $i$가 없다. 두 조건 모두 공허하게 참이다.
• 귀납 단계 ($k$ → $k+1$): $I_k$가 성립한다고 가정.
  1. 조건 2에 의해 뒤쪽 구간 $a[k..n-1]$의 모든 원소는 앞쪽 구간의 모든 원소보다 크다. $(k+1)$번째 루프는 뒤쪽 구간의 최솟값을 $a[k]$ 자리로 옮기므로, 새로운 $a[k]$도 앞쪽 전체보다 크다. 조건 1과 합치면 $a[0] < a[1] < \cdots < a[k]$가 성립한다.
  2. 그 $a[k]$는 옮겨지기 전 $a[k..n-1]$의 최솟값이었으므로 남은 모든 $x > k$에서 $a[k] < a[x]$이고, 앞쪽 원소들은 귀납 가정에서 이미 그들보다 작다. 따라서 모든 $i < k+1$, $x \ge k+1$에서 $a[i] < a[x]$.

두 조건이 모두 성립하므로 $I_{k+1}$이 참. 귀납에 의해 모든 $k$에서 $I_k$가 성립한다. $\square$

재귀 버전

같은 알고리즘을 재귀로 쓰면 한결 짧다.

void sort(int a[], int n) {
    if (n <= 1) return;     // Base
    int m = 0;
    for (int j = 0; j < n; j++) {
        if (a[m] > a[j]) m = j;
    }
    // 가장 작은 원소를 맨 앞으로
    int t = a[0]; a[0] = a[m]; a[m] = t;
    sort(a + 1, n - 1);     // 나머지 n-1개를 재귀 정렬
}

핵심 통찰은 이렇다. “전체에서 가장 작은 원소가 맨 앞으로 왔다면, 나머지만 잘 정렬되면 전체가 정렬된 것이다.”

재귀 버전의 증명

명제 $P(n)$을 “sort(a, n)이 길이 $n$의 배열을 올바르게 정렬한다”로 두자.

• Base ($n \le 1$): 길이 0 또는 1 배열은 이미 정렬되어 있다. 코드는 즉시 반환한다(if (n <= 1) return;). 성립.
• Step: $P(n-1)$이 참이라 가정. 길이 $n$ 배열에서:
  1. for문 종료 후 $a[0]$은 $a[0..n-1]$ 중 최솟값이다. 즉, 모든 $x > 0$에 대해 $a[0] < a[x]$.
  2. sort(a+1, n-1)은 귀납 가정에 의해 $a[1..n-1]$을 올바르게 정렬한다. 따라서 $a[1] < a[2] < \cdots < a[n-1]$.
  3. 1번에 의해 $a[0] < a[1]$도 성립하므로, $a[0] < a[1] < \cdots < a[n-1]$. $P(n)$이 참.

귀납에 의해 모든 $n \ge 1$에서 $P(n)$이 성립한다. $\square$

시간 복잡도

바깥쪽 루프는 $n$번 돈다. 위 코드의 안쪽 루프는 j = i부터 시작하므로, $i$번째 바깥쪽 루프에서 비교는 정확히 $n - i$번 일어난다. 따라서 총 비교 횟수는

$$\sum_{i=0}^{n-1}(n - i) = n + (n-1) + \cdots + 1 = \frac{n(n+1)}{2} = \Theta(n^2)$$

이다. (안쪽 루프를 j = i+1부터 시작하는 구현이라면 $\frac{n(n-1)}{2}$이며, 어느 쪽이든 $\Theta(n^2)$이다.)

$$T(n) = \Theta(n^2)$$

최선/평균/최악 모두 같다. 입력 분포에 무관하게 항상 $n^2$이다.

---

Merge Sort

merge sort의 아이디어는 한 문장으로 요약된다.

정렬된 두 배열을 합치면 정렬된 배열을 만들 수 있다. 그러니 배열을 반으로 쪼개 각각 정렬하고, 그 결과를 합치자.

쪼개진 부분 배열은 또 같은 방식으로 정렬한다 — 자연스러운 재귀 구조다.

Merge 단계

두 정렬된 배열을 합치는 연산은 두 포인터(two-pointer) 로 단순하게 수행된다. 각 배열의 앞부터 작은 값을 골라 결과 배열에 차례로 채운다.

void merge(int a[], int h, int n, int b[]) {
    // a[0..h-1], a[h..n-1]는 각각 정렬되어 있다고 가정
    int i = 0, j = h, k = 0;
    while (i < h && j < n) {
        if (a[i] <= a[j]) b[k++] = a[i++];
        else              b[k++] = a[j++];
    }
    while (i < h) b[k++] = a[i++];
    while (j < n) b[k++] = a[j++];
    for (int x = 0; x < n; x++) a[x] = b[x];
}

각 단계는 $O(1)$이며 포인터는 한쪽씩만 전진하므로, 길이 $n$의 두 배열을 합치는 데 $O(n)$ 이 든다.

여기서 같은 값이 있을 때 어느 쪽을 먼저 뽑는가가 안정성을 좌우한다. 위 코드는 a[i] <= a[j]이므로 값이 같으면 왼쪽(앞 절반) 원소를 먼저 결과에 넣는다. 덕분에 원래 순서가 보존되어 merge sort는 안정 정렬(stable sort) 이 된다. (만약 <를 썼다면 같은 값에서 오른쪽이 먼저 나와 불안정해질 수 있다.)

재귀 코드

void sort(int a[], int n) {
    if (n <= 1) return;     // Base
    int h = n / 2;
    sort(a, h);             // 왼쪽 절반 정렬
    sort(a + h, n - h);     // 오른쪽 절반 정렬
    std::vector<int> b(n);  // 보조 배열 (표준 C++에서 int b[n]은 가변 길이 배열이라 비표준)
    merge(a, h, n, b.data());  // 두 정렬 결과를 합쳐 a[]에 덮어쓰기
}

정렬됨의 증명

명제 $P(n)$: “sort(a, n)은 $a[\,]$를 올바르게 정렬한다.”

• Base ($n \le 1$): 즉시 반환. 정렬 필요 없음.
• Step: $P(k)$가 모든 $k < n$에서 참이라 가정 (강한 귀납법). 길이 $n$ 배열에서:
  1. sort(a, h)는 귀납 가정($h < n$)에 의해 $a[0..h-1]$을 정렬한다.
  2. sort(a+h, n-h)도 마찬가지로 $a[h..n-1]$을 정렬한다.
  3. merge가 올바르다면, 두 정렬된 부분을 합친 결과는 전체 정렬이다.

merge 자체의 올바름도 불변식으로 보일 수 있다. 불변식: 결과 배열 b[0..k-1]에는 두 입력 구간에서 지금까지 본 원소 중 가장 작은 $k$개가 정렬된 채 담겨 있다. 매 단계 두 포인터가 가리키는 값 중 더 작은 것을 b[k]에 넣으므로, 그 값은 아직 남은 어떤 원소보다도 작거나 같아 정렬 순서가 유지된다. 두 구간을 모두 소진하면 b는 전체가 정렬된 상태가 된다. $\square$

멀티셋 조건은 코드 어디서도 값을 새로 만들거나 버리지 않으므로 자동 보존된다.

시간 복잡도 — $O(n \log n)$ 유도

merge 비용 $cn$과 두 번의 재귀 호출로 점화식이 세워진다. 코드는 h = n / 2로 잘라 $\lfloor n/2 \rfloor$와 $\lceil n/2 \rceil$로 나누므로, 정확히 쓰면 이렇다.

$$T(n) = T\!\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + T\!\left(\left\lceil \frac{n}{2} \right\rceil\right) + cn$$

아래 전개는 $n$이 $2$의 거듭제곱이라고 가정해 두 항을 $T(n/2)$로 합친 형태다. 바닥·천장이 붙어도 결과는 $\Theta(n \log n)$으로 같지만, 전개가 훨씬 지저분해지므로 여기서는 단순화한 쪽을 따라간다.

$$T(n) = 2T\!\left(\frac{n}{2}\right) + cn$$

전개하면 다음과 같다.

$$\begin{aligned} T(n) &= 2T(n/2) + cn \\ &= 2\bigl(2T(n/4) + c(n/2)\bigr) + cn = 4T(n/4) + 2cn \\ &= 8T(n/8) + 3cn \\ &\;\;\vdots \\ &= 2^{\log_2 n} T(1) + cn \log_2 n \\ &= n + cn \log_2 n \\ &= O(n \log n) \end{aligned}$$

재귀 트리로도 같은 결과를 얻는다. 각 레벨의 총 작업량이 $cn$으로 같고, 트리 깊이가 $\log_2 n$이므로 총합 $cn \log_2 n$.

$$T(n) = \Theta(n \log n)$$

입력에 무관하게 최선·평균·최악 모두 $\Theta(n \log n)$이다. 대신 추가 배열 $b[\,]$를 위한 $O(n)$ 메모리가 필요하다.

---

Quick Sort

quick sort도 분할 정복이지만 분할 방식이 다르다. 정확히 반으로 자르지 않고, pivot이라 부르는 한 원소를 기준으로 “작은 것은 왼쪽, 큰 것은 오른쪽”으로 나눈다.

알고리즘

배열 $a[\,]$에서 pivot $p$를 하나 고른다(여기서는 $a[0]$). 다음을 만족하도록 $a$를 재배치한다.

• $a[d] = p$
• $a[0], a[1], \ldots, a[d-1] < p$
• $a[d+1], a[d+2], \ldots, a[n-1] > p$

여기서는 중복 없는 입력을 가정해 $< p$, $> p$ 두 구역으로 나눈다. pivot과 같은 값이 여러 개라면 규칙을 정해야 한다. 같은 값을 한쪽($\le p$, $> p$)으로 몰아넣거나, $< p$ · $= p$ · $> p$의 세 구역(3-way partition) 으로 나누는 방식이 흔하다. 후자는 중복이 많은 입력에서 특히 효율적이다.

위 그림은 pivot 7을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 모으고 7이 가운데 최종 자리에 놓이는 모습을 보여준다.

이 재배치 이후 $a[d]$의 자리는 이미 최종 위치다. pivot보다 작은 모든 값이 왼쪽에, 큰 모든 값이 오른쪽에 있으므로 $a[d]$의 인덱스가 곧 정렬 후의 자리다. 남은 일은 왼쪽 영역과 오른쪽 영역을 각각 재귀적으로 정렬하는 것뿐이다.

재귀 코드

void qsort(int a[], int n) {
    if (n <= 1) return;     // Base (길이 0, 1은 정렬 불필요)
    int p = a[0];           // pivot
    int d = partition(a, n, p);
    // 이 시점에서:
    //   a[d] == p
    //   a[0], ..., a[d-1] < p
    //   a[d+1], ..., a[n-1] > p
    qsort(a, d);             // 왼쪽 영역
    qsort(a + d + 1, n - d - 1);  // 오른쪽 영역
}

partition은 다음과 같이 한 번의 패스로 $d$를 정한다. 경계 인덱스 s를 두고, pivot보다 작은 값을 만날 때마다 앞쪽으로 모은 뒤 마지막에 pivot을 그 경계로 보낸다.

int partition(int a[], int n, int p) {  // p == a[0]
    int s = 0;                  // a[1..s]까지 < p가 모인 경계
    for (int i = 1; i < n; i++) {
        if (a[i] < p) { s++; swap(a[s], a[i]); }
    }
    swap(a[0], a[s]);           // pivot을 경계 자리로 → 최종 위치
    return s;                   // d = s
}

이렇게 정해진 $d$에서 pivot이 최종 위치에 놓인다. pivot의 위치는 입력에 따라 달라지며, 양쪽 영역의 크기가 같다는 보장은 없다. 미리 위치를 통제할 필요도 없다 — 양쪽이 서로 독립적이기 때문이다.

정렬됨의 증명

명제 $P(n)$: “qsort(a, n)은 $a[\,]$를 올바르게 정렬한다.”

• Base ($n \le 1$): 길이 0 또는 1이면 이미 정렬되어 있다. 즉시 반환.
• Step: $P(k)$가 모든 $k < n$에서 참이라 가정.
  1. partition 직후, 모든 $x < d$에 대해 $a[x] < p = a[d]$이고, 모든 $y > d$에 대해 $a[y] > a[d]$.
  2. qsort(a, d)는 귀납 가정에 의해 $a[0..d-1]$을 정렬한다. 그 결과 $a[0] < a[1] < \cdots < a[d-1]$. 또한 이 호출은 멀티셋 조건을 유지하므로, 정렬 후에도 모든 $a[x]\,(x < d)$가 여전히 $p$보다 작다.
  3. qsort(a+d+1, n-d-1)도 마찬가지로 $a[d+1..n-1]$을 정렬하고, 그 값들은 여전히 $p$보다 크다.
  4. 따라서 (왼쪽 구간이 비어 있지 않다면) $a[d-1] < a[d]$, (오른쪽 구간이 비어 있지 않다면) $a[d] < a[d+1]$이 성립한다. $d = 0$이면 왼쪽이, $d = n-1$이면 오른쪽이 빈 구간이라 해당 비교는 따질 대상이 없다. 두 경우를 합치면 전체적으로 $a[0] < \cdots < a[d-1] < a[d] < a[d+1] < \cdots < a[n-1]$. $P(n)$이 참. $\square$

시간 복잡도

partition은 $O(n)$이다. 점화식은 pivot이 어디로 가느냐에 달려 있다.

• 최선 (pivot이 항상 중앙): $T(n) = 2T(n/2) + cn = \Theta(n \log n)$. Merge Sort와 동일.
• 최악 (pivot이 항상 끝): 한쪽은 길이 0, 다른 쪽은 $n-1$. $T(n) = T(n-1) + cn = \Theta(n^2)$. Selection Sort와 유사.

이미 정렬된 배열에 항상 $a[0]$을 pivot으로 잡으면 정확히 최악 경우가 된다.

평균은 왜 $\Theta(n \log n)$일까? 먼저 “평균”이 무엇에 대한 평균인지 정해야 한다. 여기서는 서로 다른 $n$개의 키를 두고, pivot을 균등 무작위로 고른다고 하자(또는 입력 순서가 $n!$가지 순열 중 균등하게 뽑힌다고 두어도 같다). 그러면 pivot의 등수가 $1$부터 $n$까지 각각 확률 $\frac{1}{n}$이 된다.

“분할이 대체로 균형 잡힌다”는 감각만으로는 기대 비교 횟수가 나오지 않는다. 실제로 세는 방법은 두 가지다.

기대 점화식. 등수 $k$가 확률 $\frac1n$로 나오므로

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

이고, 이를 풀면 $\Theta(n \log n)$이 나온다.

쌍마다 세기. 더 짧은 길도 있다. 정렬 후 등수가 $i < j$인 두 원소는, $i$부터 $j$까지의 등수 중 가장 먼저 pivot이 되는 것이 그 둘 중 하나일 때에만 서로 비교된다. 그 사이 어떤 값이 먼저 pivot이 되면 둘은 다른 구간으로 갈라져 영영 만나지 않는다. 후보가 $j - i + 1$개이므로 확률은 $\frac{2}{j-i+1}$이고, 모든 쌍에 대해 더하면

$$E(n) = \sum_{i<j} \frac{2}{j-i+1} = 2(n+1)H_n - 4n \approx 2n \ln n$$

이다. $H_n$은 조화수다. 유도 전체는 quick sort 평균 분석에서 따로 다룬다.

그런데 왜 빠른가?

이론적 최악 복잡도가 $O(n^2)$인데도 Quick Sort는 실제로 Merge Sort보다 종종 더 빠르게 관찰된다(구체적인 차이는 입력 분포·구현·하드웨어에 따라 달라진다). 이유를 정리하면 다음과 같다.

• 기대 시간이 $\Theta(n \log n)$. 무작위로 pivot을 고르면 최악 분할이 매번 일어날 확률이 매우 작아진다. 다만 무작위 pivot에서도 최악 분할 자체가 불가능한 것은 아니므로, “확률적으로 사라진다”기보다 기대 시간이 $\Theta(n \log n)$이라고 말하는 것이 정확하다.
• 제자리 정렬(in-place). Merge Sort가 매 단계 추가 배열을 쓰는 반면, Quick Sort는 원본 배열 안에서 교환만으로 분할이 가능하다. 캐시 지역성이 좋고 메모리 할당 오버헤드가 없다. (단, 재귀 호출 스택은 평균 $O(\log n)$, 최악 $O(n)$을 따로 쓴다.)
• 상수 계수가 작다. partition은 배열을 한 번의 순차 패스로 훑으며 제자리에서 교환만 한다. 접근이 순차적이라 캐시 라인을 낭비 없이 쓰고, 보조 배열이 없으니 할당과 복사가 없다. 반면 비교 결과에 따른 분기는 무작위 데이터에서 예측이 잘 맞지 않는 편이며, 최근 구현들이 분기 없는(branchless) partition을 쓰는 이유가 여기에 있다. 즉 빠른 이유는 분기 예측이 아니라 메모리 접근 쪽이다.

세 가지가 합쳐져, 같은 $\Theta(n \log n)$이라도 실측 성능 차이가 크게 벌어진다.

---

세 알고리즘 비교

	Selection Sort	Merge Sort	Quick Sort
최선	$\Theta(n^2)$	$\Theta(n \log n)$	$\Theta(n \log n)$
평균	$\Theta(n^2)$	$\Theta(n \log n)$	$\Theta(n \log n)$
최악	$\Theta(n^2)$	$\Theta(n \log n)$	$\Theta(n^2)$
추가 메모리 (보조 배열)	$O(1)$	$O(n)$	$O(1)$
재귀 호출 스택	$O(1)$ (반복문 버전)	$O(\log n)$	$O(\log n)$ 평균 / $O(n)$ 최악
안정성	불안정 (일반 swap 구현)	안정	불안정 (제자리 partition)
입력 의존성	없음	없음	pivot 선택에 민감
핵심 아이디어	매 단계 최솟값 선택	분할 + 병합	분할 + pivot 배치

추가 메모리 행은 보조 배열만 따진 것이다. Quick Sort의 $O(1)$도 partition 자체의 메모리이며, 재귀 호출 스택은 위 행처럼 따로 든다.