정렬 알고리즘 (퀵, 병합, 안정)
정렬은 컴퓨터 과학에서 가장 오래 연구된 문제이자 실무에서 가장 자주 마주치는 작업이다. 데이터를 보여주기 위해, 검색을 빠르게 하기 위해, 중복을 제거하기 위해, 통계를 계산하기 위해 — 어느 방향으로 가도 결국 정렬이 한 번 끼어든다. 본 글은 입문자가 반드시 익혀야 할 여덟 가지 핵심 정렬 알고리즘을 시간복잡도·안정성·실전 채택 기준으로 비교하면서 세심하게 정리한다(출처: CLRS — Introduction to Algorithms). 제가 학교 알고리즘 수업에서 같은 100만 개 데이터를 버블 정렬과 퀵 정렬로 비교 측정해 본 후 시간 차이가 1000배가 넘는 모습을 직접 본 후로는 "정렬 알고리즘 선택 한 줄이 시스템의 응답 시간을 결정한다"는 사실을 손끝으로 받아들였다.
정렬 알고리즘의 평가 기준 — 시간복잡도와 안정성
정렬 알고리즘을 평가할 때 가장 자주 쓰이는 세 가지 기준이 있다. 첫째는 시간복잡도, 둘째는 공간복잡도, 셋째는 안정성(stability)이다. 시험과 실무 모두에서 자주 묻는 항목이므로 각 기준의 의미를 정확히 외워두는 것이 중요하다.
안정성(Stability)이란 같은 키를 가진 원소들의 상대 순서가 정렬 후에도 유지되는 성질을 의미한다. 예를 들어 학생 명단을 점수로 정렬할 때, 같은 점수를 가진 학생들의 입력 순서가 그대로 보존되면 안정 정렬이고, 뒤바뀔 수 있으면 불안정 정렬이다. 데이터베이스의 다중 키 정렬(먼저 학과로, 그 안에서 점수로)을 안정 정렬로 처리해야 의도한 결과가 나오기 때문에 실무에서 의외로 중요한 성질이다.
제자리 정렬(In-place)이란 입력 배열 외에 O(1) 또는 O(log n)의 매우 적은 추가 메모리만 사용하는 정렬을 의미한다. 메모리 효율이 중요한 환경(임베디드·대용량 데이터)에서는 제자리 정렬 여부가 알고리즘 선택의 결정적 기준이 된다. 솔직히 제 경험상 학교에서는 시간복잡도만 주로 다뤘지만, 인턴십에서 메모리 1GB 컨테이너 안에 4GB짜리 데이터를 정렬해야 하는 상황을 마주한 후로는 안정성과 제자리 여부가 시간복잡도만큼이나 결정적이라는 점을 받아들였다.
여덟 가지 핵심 정렬을 한 표로 비교하면 다음과 같다.
| 알고리즘 | 평균 | 최악 | 공간 | 안정성 | 제자리 | 대표 채택 |
|---|---|---|---|---|---|---|
| 버블 정렬 | O(n²) | O(n²) | O(1) | 안정 | ✓ | 교육용·매우 작은 데이터 |
| 선택 정렬 | O(n²) | O(n²) | O(1) | 불안정 | ✓ | 교육용 |
| 삽입 정렬 | O(n²) | O(n²) | O(1) | 안정 | ✓ | 거의 정렬된 작은 데이터 |
| 셸 정렬 | O(n^1.3) | O(n²) | O(1) | 불안정 | ✓ | 중간 크기 데이터 |
| 퀵 정렬 | O(n log n) | O(n²) | O(log n) | 불안정 | ✓ | C qsort, std::sort 기반 |
| 병합 정렬 | O(n log n) | O(n log n) | O(n) | 안정 | × | Java Arrays.sort (객체), Python Timsort |
| 힙 정렬 | O(n log n) | O(n log n) | O(1) | 불안정 | ✓ | 최악 보장 필요 시 |
| 기수 정렬 | O(d·n) | O(d·n) | O(n + k) | 안정 | × | 정수·고정 길이 키 |
단순 정렬 3종 — 버블·선택·삽입
평균 O(n²)을 가지는 단순 정렬 세 가지는 실무 성능은 떨어지지만 학습 순서로는 거의 예외 없이 가장 먼저 배운다. 동작 원리가 직관적이고 코드가 짧기 때문이다.
버블 정렬(Bubble Sort)은 인접한 두 원소를 비교해 잘못된 순서면 교환하는 작업을 끝까지 반복한다. 한 번의 외부 반복마다 가장 큰 값이 거품처럼 오른쪽 끝으로 떠오르는 모습에서 이름이 유래했다. 가장 단순하지만 가장 느린 정렬 중 하나이며, 100만 개 데이터에서는 사실상 사용 불가능하다.
선택 정렬(Selection Sort)은 미정렬 구간에서 최솟값을 찾아 정렬된 구간의 끝에 두는 작업을 반복한다. 비교 횟수는 버블 정렬과 같지만 교환 횟수가 훨씬 적어 약간 빠르다는 차이가 있다. 다만 같은 키의 원소가 뒤로 밀려나면서 상대 순서가 깨지므로 불안정 정렬이다.
삽입 정렬(Insertion Sort)은 카드 게임에서 카드를 한 장씩 들고 적절한 자리에 끼워 넣는 동작과 정확히 같다. 거의 정렬된 데이터(예: 정렬된 배열에 새 원소 몇 개 추가)에서는 O(n)에 가까운 시간이 나오기 때문에, 작은 부분 배열에 한해서 실무 정렬의 보조 알고리즘으로 자주 쓰인다.
def insertion_sort(a):
for i in range(1, len(a)):
key = a[i]; j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key분할 정복 정렬 3종 — 퀵·병합·힙
평균 O(n log n) 정렬은 단순 정렬과 비교해 같은 데이터에서 수십~수백 배 빠르며, 사실상 모든 실무 정렬이 이 부류에 속한다. 셋 다 분할 정복(Divide and Conquer) 또는 트리 기반의 아이디어를 공유한다.
퀵 정렬(Quick Sort)은 1959년 토니 호어(Tony Hoare)가 제안한 가장 널리 채택된 정렬이다(출처: Wikipedia — Quicksort). 한 원소(pivot)를 기준으로 작은 값과 큰 값을 양쪽에 분리한 뒤, 두 부분 배열을 재귀적으로 정렬한다. 여기서 pivot이란 분할의 기준이 되는 원소를 가리키며, 그 선택 전략(첫·마지막·중앙·임의·중위 3 등)이 성능을 좌우한다. 평균 O(n log n)이지만 운이 나쁘면 최악 O(n²)으로 떨어진다는 약점이 있다. 그럼에도 캐시 효율이 좋고 제자리 정렬이 가능하다는 두 강점 덕분에 C의 qsort, C++의 std::sort, Linux 커널 내부 정렬이 모두 퀵 정렬 변형을 채택하고 있다.
def quick_sort(a, lo=0, hi=None):
if hi is None: hi = len(a) - 1
if lo >= hi: return
pivot = a[(lo + hi) // 2]
i, j = lo, hi
while i <= j:
while a[i] < pivot: i += 1
while a[j] > pivot: j -= 1
if i <= j:
a[i], a[j] = a[j], a[i]
i += 1; j -= 1
quick_sort(a, lo, j)
quick_sort(a, i, hi)병합 정렬(Merge Sort)은 1945년 폰 노이만(John von Neumann)이 제안한 가장 안정적인 O(n log n) 정렬이다. 배열을 절반으로 나눠 각각 정렬한 뒤, 두 정렬된 배열을 한 줄로 병합(merge)한다. 최악도 O(n log n)을 보장하고 안정 정렬이라는 두 가지 강점이 결정적이다. 다만 병합 과정에서 O(n)의 추가 메모리가 필요해 제자리 정렬이 아니라는 단점이 있다. Java의 Arrays.sort(객체 배열), Python의 표준 sorted·list.sort가 사용하는 Timsort가 병합 정렬 기반의 하이브리드이며, 거의 모든 실무 표준 정렬의 토대이다.
힙 정렬(Heap Sort)은 이전 글에서 다룬 힙 자료구조를 활용하는 정렬이다. 입력을 한 번 힙으로 만든 뒤 n번 추출하면 정렬된 결과가 나온다. 최악도 O(n log n)을 보장하고 제자리 정렬이지만, 캐시 효율이 퀵 정렬보다 떨어져 실무에서는 잘 채택되지 않는다. 다만 최악 시간 보장이 중요한 영역(실시간 시스템·임베디드)에서는 힙 정렬이 안전한 선택지가 된다.
비교 기반의 하한과 비비교 정렬 — 기수 정렬
비교 기반 정렬의 시간복잡도는 정보이론적으로 Ω(n log n) 이라는 하한이 증명되어 있다. 즉 비교 두 원소의 대소 비교만으로 정렬하는 어떤 알고리즘도 평균 O(n log n)보다 빨라질 수 없다는 의미다(출처: Wikipedia — Comparison sort lower bound). 그렇다면 더 빠른 정렬이 없는가 하면, 비교를 하지 않는 비교 외 정렬들은 이 하한을 우회할 수 있다.
기수 정렬(Radix Sort)은 키의 자릿수를 한 자리씩 비교하는 정렬로, 자릿수 d와 원소 수 n에 대해 O(d·n) 시간이 든다. d가 상수에 가까우면 사실상 O(n)에 정렬되는 셈이며, 정수·문자열·고정 길이 키에 적용 가능하다. 다만 부동소수점이나 임의의 구조체에는 적용이 까다롭다는 한계가 있다. 시험 답안에서 자주 묻는 항목으로 계수 정렬(Counting Sort)과 버킷 정렬(Bucket Sort)도 비비교 정렬이며, 같은 부류에 속한다.
def counting_sort(a, max_val):
count = [0] * (max_val + 1)
for x in a:
count[x] += 1
out = []
for i, c in enumerate(count):
out.extend([i] * c)
return out
print(counting_sort([3, 1, 4, 1, 5, 9, 2, 6, 5, 3], 9))
# [1, 1, 2, 3, 3, 4, 5, 5, 6, 9]마지막으로 시험과 실무 모두에서 자주 쓰이는 한 줄 요약을 정리하면, "정렬 알고리즘은 평균 O(n²)인 단순 정렬(버블·선택·삽입), 평균 O(n log n)인 분할 정복 정렬(퀵·병합·힙), 그리고 비비교 정렬(기수·계수)로 분류된다. 실무에서는 거의 모든 표준 라이브러리가 병합 정렬 기반의 하이브리드(Timsort) 또는 퀵 정렬 변형을 채택한다"는 두 문장이 표준 답안 표현으로 통한다. 솔직히 제 경험상 학교에서는 알고리즘을 외워야 할 항목으로 봤지만, 인턴십에서 표준 라이브러리가 어떤 정렬을 쓰는지 직접 확인한 후로는 정렬이 단순한 시험 영역이 아니라 매일 사용하는 도구라는 점을 받아들였다. 다음 글에서는 정렬·탐색을 활용하는 더 깊은 알고리즘 영역(분할 정복·DP·그리디)으로 이어진다.
메타 디스크립션: 8가지 핵심 정렬 알고리즘(버블·선택·삽입·셸·퀵·병합·힙·기수)의 시간복잡도·안정성·제자리 여부·실무 채택 비교와 코드 예시를 자료구조 입문자 관점에서 세심하게 정리합니다.