정렬 알고리즘 — 면접관이 QuickSort를 물어보는 진짜 이유
"퀵 정렬의 동작 원리를 설명해주세요"라는 질문의 의도는 정렬 자체가 아닙니다. 분할 정복, 최악의 경우 분석, 안정성의 의미 — 정렬 하나로 이런 개념들을 한꺼번에 확인할 수 있기 때문입니다.
정렬 알고리즘을 제대로 이해하면, 알고리즘 설계의 핵심 원리(분할 정복, 트레이드오프, 실무 선택 기준)가 함께 잡힙니다.
개념 정의
정렬 알고리즘 은 데이터를 특정 기준에 따라 순서대로 나열하는 알고리즘입니다. 핵심은 "어떻게 비교하고 교환하는가"에 따라 시간/공간 복잡도와 안정성이 달라진다는 것입니다.
전체 비교
| 정렬 | 평균 | 최악 | 공간 | 안정성 |
|---|---|---|---|---|
| 버블 정렬 | O(n²) | O(n²) | O(1) | 안정 |
| 선택 정렬 | O(n²) | O(n²) | O(1) | 불안정 |
| 삽입 정렬 | O(n²) | O(n²) | O(1) | 안정 |
| 머지 정렬 | O(n log n) | O(n log n) | O(n) | ** 안정** |
| ** 퀵 정렬** | O(n log n) | O(n²) | O(log n) | 불안정 |
| 힙 정렬 | O(n log n) | O(n log n) | O(1) | 불안정 |
| 팀 정렬 | O(n log n) | O(n log n) | O(n) | 안정 |
O(n²) 정렬은 개념만 알면 되고, 깊이 이해해야 하는 건 퀵 정렬과 머지 정렬입니다.
퀵 정렬 (Quick Sort)
** 분할 정복 **의 대표적인 예입니다.
동작 원리
- ** 피벗(pivot)** 선택 — 보통 배열의 첫 번째, 마지막, 또는 중간 요소
- ** 분할(partition)** — 피벗보다 작은 건 왼쪽, 큰 건 오른쪽으로 분리
- 왼쪽과 오른쪽에 대해 ** 재귀적으로 반복**
[3, 6, 8, 10, 1, 2, 1] 피벗: 3
분할 후:
[1, 2, 1] [3] [6, 8, 10]
왼쪽 재귀: [1, 1, 2]
오른쪽 재귀: [6, 8, 10]
결과: [1, 1, 2, 3, 6, 8, 10]
왜 최악이 O(n²)인가
이미 정렬된 배열에서 맨 앞을 피벗으로 고르면:
[1, 2, 3, 4, 5] 피벗: 1
분할: [] [1] [2, 3, 4, 5]
다음 피벗: 2
분할: [] [2] [3, 4, 5]
...
매번 한 쪽에 n-1개가 몰림 → 분할이 n번 → O(n²)
편향 분할이 발생하면 분할 정복의 이점이 사라집니다.
최악을 피하는 방법
- ** 랜덤 피벗** — 임의의 요소를 피벗으로 선택
- Median-of-Three — 첫 번째, 중간, 마지막 중 중앙값을 피벗으로 사용
- Introsort — 재귀 깊이가 너무 깊어지면 힙 정렬로 전환 (C++의
std::sort)
머지 정렬 (Merge Sort)
역시 분할 정복입니다. 퀵 정렬과 달리 ** 항상 O(n log n)**이 보장됩니다.
동작 원리
- 배열을 ** 반으로 분할** (재귀)
- 각각 정렬
- 정렬된 두 배열을 ** 병합 (merge)**
[38, 27, 43, 3, 9, 82, 10]
분할:
[38, 27, 43] [3, 9, 82, 10]
더 분할:
[38] [27, 43] [3, 9] [82, 10]
정렬 & 병합:
[38] [27, 43] → [27, 38, 43]
[3, 9] [10, 82] → [3, 9, 10, 82]
최종 병합:
[3, 9, 10, 27, 38, 43, 82]
왜 O(n) 추가 공간이 필요한가
병합할 때 두 배열을 비교하면서 새 배열에 넣어야 합니다. 제자리(in-place)로 하면 구현이 복잡하고 성능도 떨어집니다.
안정 정렬 vs 불안정 정렬
** 안정 정렬(Stable Sort)**: 같은 값을 가진 요소의 ** 상대 순서가 유지 **됩니다.
[(김, 90), (이, 85), (박, 90)]을 점수로 정렬할 때
안정: [(이, 85), (김, 90), (박, 90)] ← 김이 박보다 먼저 (원래 순서 유지)
불안정: [(이, 85), (박, 90), (김, 90)] ← 순서가 바뀔 수 있음
안정 정렬이 필요한 경우: 이름순으로 정렬한 뒤 점수순으로 다시 정렬할 때, 안정 정렬이어야 같은 점수 내에서 이름순이 유지됩니다.
Java의 정렬은 뭘 쓸까
Arrays.sort()— primitive 배열은 Dual-Pivot Quicksort, Object 배열은 TimSortCollections.sort()— 내부적으로 TimSort (안정 정렬)
Object 배열에 안정 정렬을 쓰는 이유는, 객체를 정렬할 때 상대 순서 보존이 중요한 경우가 많기 때문입니다.
TimSort란?
머지 정렬 + 삽입 정렬의 하이브리드입니다. 실제 데이터에서는 부분적으로 정렬된 경우가 많은데, 이 특성을 활용합니다.
- 배열을 "run"이라는 이미 정렬된 구간으로 분할
- 작은 run은 삽입 정렬로 확장 (작은 배열에서 삽입 정렬이 빠름)
- run들을 머지 정렬로 병합
거의 정렬된 데이터에서 O(n)에 가까운 성능을 보입니다. Python의 기본 정렬도 TimSort입니다.
주의할 점
퀵 정렬의 최악 O(n²)을 무시하는 실수
"퀵 정렬은 O(n log n)"이라고만 외우면, 이미 정렬된 배열에서 맨 앞을 피벗으로 잡았을 때 왜 시간 초과가 나는지 설명할 수 없습니다. 코딩 테스트에서 정렬된 입력이 주어지는 경우가 의외로 많기 때문에, ** 피벗 선택 전략 **을 반드시 고려해야 합니다.
안정 정렬을 무시하고 다중 기준 정렬이 깨지는 경우
이름순으로 정렬한 뒤 점수순으로 다시 정렬할 때, 불안정 정렬을 쓰면 같은 점수 내에서 이름 순서가 뒤섞입니다. ** 다중 기준 정렬이 필요한 상황 **에서는 반드시 안정 정렬을 써야 합니다.
비교 기반 정렬의 O(n log n) 하한을 모르는 경우
비교 기반 정렬은 ** 아무리 최적화해도 O(n log n)보다 빠를 수 없습니다 **. n개 요소의 n!가지 순열을 구분하려면 최소 log₂(n!) ≈ n log n번의 비교가 필요하기 때문입니다. 이 하한을 이해해야 "O(n) 정렬이 가능한가?"라는 질문에 정확히 답할 수 있습니다.
비교 없이 정렬하면 O(n)이 가능합니다 — 카운팅 정렬, 기수 정렬, 버킷 정렬. 단, 모두 입력 조건(값의 범위, 자릿수 등)이 제한적입니다.
퀵 정렬이 머지 정렬보다 빠른 이유
이론적 복잡도는 같은데(O(n log n)), 실제로는 퀵 정렬이 빠른 경우가 많습니다.
- ** 캐시 적중률** — 퀵 정렬은 연속된 메모리를 접근하지만, 머지 정렬은 여러 배열을 왔다 갔다 합니다.
- ** 추가 메모리 불필요** — 머지 정렬은 O(n) 공간이 필요합니다.
- ** 상수 계수** — 퀵 정렬의 내부 루프가 더 단순합니다.
다만 ** 예측 가능성 **이 중요한 경우(최악을 허용할 수 없는 경우)에는 머지 정렬이 더 안전합니다.
정리
| 항목 | 핵심 |
|---|---|
| 퀵 정렬 | 분할 정복, 평균 O(n log n), 최악 O(n²), 불안정 |
| 머지 정렬 | 분할 정복, 항상 O(n log n), O(n) 추가 공간, 안정 |
| 안정 정렬 | 같은 값의 상대 순서가 유지됨 (다중 기준 정렬에 필수) |
| 비교 하한 | 비교 기반 정렬은 O(n log n)보다 빠를 수 없음 |
| Java Arrays.sort() | primitive → Dual-Pivot Quicksort, Object → TimSort |
| TimSort | 머지 정렬 + 삽입 정렬 하이브리드, 부분 정렬 활용 |
| 실무 | 직접 구현 거의 없음, Comparator로 정렬 기준 커스터마이즈 |
파생되는 개념들
- ** 분할 정복 (Divide and Conquer)** — 퀵/머지 정렬의 패러다임
- ** 외부 정렬 (External Sort)** — 메모리에 다 안 들어가는 데이터 정렬
- ** 위상 정렬 (Topological Sort)** — DAG에서의 순서 결정
- Counting Sort / Radix Sort — 비교 없는 정렬