고르는 기준은 셋입니다. 평균 시간복잡도, 같은 값의 순서가 유지되는 안정 여부, 추가 메모리를 쓰지 않는 제자리 여부입니다.
정렬 알고리즘 비교
데이터를 순서대로 배치하는 알고리즘. 상황에 따라 최적의 알고리즘이 다르다.
한눈에 비교
| 알고리즘 | 평균 | 최악 | 공간 | 안정 |
|---|---|---|---|---|
| 버블 | 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: 실제 데이터의 "거의 정렬된 부분"을 활용하여 삽입 정렬 + 병합 정렬을 결합한 하이브리드.