🟣 큰 문제를 반으로 접는다
앞 장에서 T(n) = 2T(n/2) + O(n)이 O(n log n)이 되는 걸 봤다. 이 점화식이 나오는 설계 방식이 분할정복이다. 큰 문제를 비슷한 크기의 작은 문제 여럿으로 나누고(분할), 각각을 재귀로 풀고(정복), 그 답을 합쳐 원래 문제의 답을 만든다(결합).
분할정복이 힘을 내는 이유는 그 점화식에 있다. 문제를 절반으로 접을 때마다 크기가 지수적으로 줄어드니, 바닥까지 내려가는 단계 수가 log n에 그친다. 결합 비용이 각 단계에서 O(n)이면 전체가 O(n log n)으로 눌린다. 정렬은 이 설계가 가장 선명하게 드러나는 문제라, 정렬을 통해 분할정복을 익히는 편이 빠르다.
🟣 병합 정렬: 나누고, 합치며 정렬한다
병합 정렬은 분할정복의 교과서다. 배열을 절반으로 나눠 각각 재귀로 정렬한 뒤, 이미 정렬된 두 배열을 하나로 합친다(merge). 합치는 일이 어렵지 않다. 두 배열의 맨 앞을 비교해 작은 쪽을 꺼내기를 반복하면, 한 번 훑는 O(n)에 정렬된 결과가 나온다.
병합 정렬의 성질 두 가지가 실무에서 중요하다. 첫째, 최악의 경우에도 O(n log n)을 보장한다. 입력이 어떻게 생겼든 항상 절반으로 나누기 때문이다. 둘째, 같은 값의 원래 순서를 유지하는 안정 정렬이다. 여러 기준으로 연달아 정렬할 때 이 성질이 요긴하다. 대가는 합칠 공간이 따로 필요해 O(n)의 추가 메모리를 쓴다는 점이다.
🟣 퀵 정렬: 기준을 잡고 갈라놓는다
퀵 정렬도 분할정복이지만 순서가 반대다. 병합 정렬은 대충 나눈 뒤 합칠 때 정렬하고, 퀵 정렬은 나눌 때 정렬해 두고 합칠 땐 아무 일도 안 한다. 기준값(pivot) 하나를 골라, 그보다 작은 값은 왼쪽으로 큰 값은 오른쪽으로 갈라놓는다(partition). 이렇게 갈라놓으면 pivot은 이미 제자리에 있고, 왼쪽과 오른쪽을 각각 재귀로 정렬하면 끝난다.
퀵 정렬은 추가 메모리 없이 배열 안에서 자리를 바꿔 가며 정렬하는 제자리(in-place) 정렬이라 상수 계수가 작고 캐시 친화적이다. 그래서 평균적으로 병합 정렬보다 빠르게 도는 경우가 많다. 문제는 최악의 경우다.
🚀 최악의 경우와 랜덤화
pivot이 매번 최솟값이나 최댓값으로 뽑히면 분할이 한쪽으로 쏠린다. 크기 n이 n-1과 0으로 갈라지면 단계 수가 log n이 아니라 n이 되어, 전체가 O(n²)으로 주저앉는다. 이미 정렬된 배열에서 맨 앞을 pivot으로 잡으면 정확히 이 일이 벌어진다. 흔한 입력에서 최악이 터지는 셈이다.
여기서 확률적 사고가 들어온다. pivot을 매번 무작위로 고르면, 특정 입력을 노려 최악을 만들려는 시도가 통하지 않는다. 어떤 입력이 오든 나쁜 분할이 연달아 일어날 확률이 지수적으로 작아지기 때문이다. 이것이 랜덤화 알고리즘의 발상이다. 입력의 분포를 가정하는 대신, 알고리즘 안에 무작위를 심어 최악 입력이라는 개념 자체를 무력화한다. 기댓값 분석으로 평균 O(n log n)이 보장되고, 그 평균이 현실에서 거의 항상 나온다.
🟣 힙 정렬: 자료구조로 정렬한다
병합 정렬은 추가 메모리를 쓰고, 퀵 정렬은 최악이 O(n²)이다. 둘의 약점을 동시에 피하는 것이 힙 정렬이다. 힙은 부모가 자식보다 항상 크거나 같은(최대 힙) 완전 이진 트리로, 배열 하나로 표현된다. 최댓값이 항상 뿌리에 있다는 성질을 이용한다.
정렬은 두 국면으로 이뤄진다. 먼저 배열을 힙 구조로 만들고(build heap), 그다음 뿌리의 최댓값을 배열 끝으로 빼내고 힙 크기를 하나 줄여 다시 힙 성질을 회복하기(heapify)를 반복한다. 최댓값을 하나씩 뒤에서부터 채우면 정렬이 완성된다. 값을 빼낼 때마다 트리 높이만큼 O(log n)이 들고 이를 n번 하니 전체가 O(n log n)이다.
힙 정렬은 추가 메모리가 상수뿐인 제자리 정렬이면서 최악에도 O(n log n)을 보장한다. 대신 안정 정렬이 아니고, 접근 패턴이 배열 곳곳을 뛰어다녀 캐시 효율이 퀵 정렬보다 나쁘다. 그래서 "최악을 반드시 막아야 하는데 메모리는 아껴야 하는" 자리에서 진가를 발휘한다.
🟣 비교로는 O(n log n)을 못 넘는다
여기까지 셋 모두 값을 서로 비교해서 정렬했다. 그런데 비교만으로 정렬하는 알고리즘은 아무리 잘 만들어도 Ω(n log n)보다 빠를 수 없다는 사실이 증명돼 있다. 근거는 결정 트리다. n개 원소의 가능한 순열은 n!가지이고, 비교 한 번은 경우를 둘로 가른다. n!가지를 구별하려면 트리 높이가 최소 log₂(n!), 곧 Ω(n log n)이어야 한다. 이 하한은 앞 장에서 본 Ω 표기가 실제로 쓰이는 대표 사례다.
이 하한은 "비교로는"이라는 단서 아래에서만 성립한다. 값을 비교하지 않고 다른 정보를 쓰면 우회할 수 있다.
🚀 기수 정렬: 비교를 버린다
기수 정렬은 값을 서로 비교하지 않는다. 대신 자릿수별로 나눠 담는다. 낮은 자리부터 그 자리 숫자를 기준으로 안정적으로 분배하기를 가장 높은 자리까지 반복하면 전체가 정렬된다. 자릿수가 d이고 각 자리의 값 범위가 k라면 복잡도는 O(d(n+k))다. d와 k가 작으면 사실상 O(n)이라 비교 정렬의 하한을 뚫는다.
공짜는 아니다. 기수 정렬은 값이 정수나 고정 길이 문자열처럼 자릿수로 쪼갤 수 있어야 하고, 자릿수 범위가 크면 오히려 손해다. 비교 정렬은 범용이지만 하한이 있고, 기수 정렬은 조건이 붙는 대신 그 하한을 넘는다는 맞바꿈이다. 하한을 우회하려면 문제에 대한 추가 가정이 반드시 필요하다는 점이 인상 깊었다.
🟣 정리
- 분할정복은 문제를 절반으로 접어 단계 수를
log n으로 누른다. 결합 비용이O(n)이면 전체가O(n log n)이 된다. - 병합 정렬은 최악에도
O(n log n)을 보장하고 안정 정렬이지만 추가 메모리를 쓴다. 퀵 정렬은 제자리라 평균이 빠르지만 pivot이 쏠리면 최악O(n²)이다. - 퀵 정렬의 최악은 pivot을 무작위로 골라 막는다. 입력을 가정하는 대신 알고리즘에 무작위를 심어 최악 입력을 무력화하는 것이 랜덤화의 핵심이다.
- 힙 정렬은 제자리이면서 최악에도
O(n log n)을 보장한다. 안정성과 캐시 효율을 내주는 대가다. - 비교 정렬은 결정 트리 논증으로
Ω(n log n)이 하한이다. 기수 정렬은 비교를 버리고 자릿수로 분배해 이 하한을 우회하되, 값의 형태에 조건이 붙는다.
정렬은 면접 단골이다. "왜 언어 표준 정렬은 하나가 아니라 여러 알고리즘을 섞어 쓰나"라는 질문의 답이 이 장에 다 있다. 실제로 많은 표준 라이브러리가 퀵 정렬로 빠르게 가다가 재귀가 너무 깊어지면 힙 정렬로 갈아타고, 작은 구간은 삽입 정렬로 마무리하는 혼합 방식을 쓴다. 각 정렬의 장단이 정확히 이 맞바꿈에서 나온다. 다음 장은 분할한 부분문제가 서로 겹칠 때 벌어지는 일, 동적 프로그래밍과 그리디다.