정렬 알고리즘 비교
데이터를 순서대로 배치하는 알고리즘. 상황에 따라 최적의 알고리즘이 다르다.
한눈에 비교
| 알고리즘 | 평균 | 최악 | 공간 | 안정 |
|---|
| 버블 | 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) | 불안정 |
동작 원리
[버블 정렬] 인접 요소 교환
5 3 8 1 → 3 5 1 8 → 3 1 5 8 → 1 3 5 8
[선택 정렬] 최솟값을 앞으로
5 3 8 1 → 1|3 8 5 → 1 3|8 5 → 1 3 5 8
[삽입 정렬] 적절한 위치에 삽입
5|3 8 1 → 3 5|8 1 → 3 5 8|1 → 1 3 5 8
[병합 정렬] 분할 후 병합
5 3 8 1 → [5,3] [8,1]
→ [3,5] [1,8] → [1,3,5,8]
[퀵 정렬] 피벗 기준 분할
5 3 8 1 (피벗=5)
→ [3,1] 5 [8] → [1,3] 5 [8]
언제 무엇을 쓸까?
| 상황 | 추천 | 이유 |
|---|
| 거의 정렬됨 | 삽입 정렬 | 최선 O(N) |
| 데이터 작음 (N<50) | 삽입 정렬 | 오버헤드 적음 |
| 일반적인 경우 | 퀵 정렬 | 평균 가장 빠름 |
| 안정성 필요 | 병합 정렬 | 안정 + O(N log N) |
| 메모리 제한 | 힙 정렬 | O(1) 추가 공간 |
| 외부 정렬 | 병합 정렬 | 순차 접근 |
안정 정렬이란?
입력: (3,A) (1,B) (3,C) (2,D)
안정: (1,B) (2,D) (3,A) (3,C)
→ 같은 키(3)의 원래 순서 유지
불안정: (1,B) (2,D) (3,C) (3,A)
→ 같은 키의 순서가 바뀔 수 있음
실무에서의 정렬
| 언어/DB | 알고리즘 |
|---|
Python sort() | Timsort (병합+삽입) |
Java Arrays.sort() | Dual-Pivot QuickSort |
JavaScript sort() | Timsort (V8) |
| PostgreSQL | 외부 병합 정렬 |
Timsort: 실제 데이터의 "거의 정렬된 부분"을 활용하여 삽입 정렬 + 병합 정렬을 결합한 하이브리드.