정렬 알고리즘 종합 비교
| 알고리즘 | 최선 | 평균 | 최악 | 공간 | 안정 | 제자리 | 특징 |
|---|
| 버블 | O(n) | O(n²) | O(n²) | O(1) | O | O | 교환 기반, 교육용, 조기종료 최적화 |
| 선택 | O(n²) | O(n²) | O(n²) | O(1) | X | O | 교환 O(n)으로 최소, 비적응적 |
| 삽입 | O(n) | O(n²) | O(n²) | O(1) | O | O | 적응적, 소규모·거의 정렬 데이터에 유리 |
| 병합 | O(n log n) | O(n log n) | O(n log n) | O(n) | O | X | 성능 보장, 외부 정렬, 안정 |
| 퀵 | O(n log n) | O(n log n) | O(n²) | O(log n) | X | O | 평균 최고 성능, 캐시 효율, 피벗 의존 |
| 힙 | O(n log n) | O(n log n) | O(n log n) | O(1) | X | O | 성능 보장, 제자리, 캐시 비효율 |
| 계수 | O(n+k) | O(n+k) | O(n+k) | O(n+k) | O | X | 비비교, 정수, 범위(k) 작을 때 |
| 기수 | O(d(n+k)) | O(d(n+k)) | O(d(n+k)) | O(n+k) | O | X | 비비교, 자릿수(d) 기반 |
TimSort vs 퀵 정렬 vs 병합 정렬
| 항목 | TimSort | 퀵 정렬 | 병합 정렬 |
|---|
| 안정성 | 안정 | 불안정 | 안정 |
| 적응형 | O (Run 활용) | X | X |
| 최악 | O(n log n) 보장 | O(n^2) | O(n log n) 보장 |
| 공간 | O(n) | O(log n) | O(n) |
| 실데이터 | 최적화 (부분정렬 활용) | 평균 빠름 | 항상 일정 |
| 적용 | Python/Java 기본 | C qsort(), 범용 | 외부 정렬 |
안정 정렬 vs 불안정 정렬
| 구분 | 안정 정렬 | 불안정 정렬 |
|---|
| 동일 키 순서 | 유지 | 보장 안 됨 |
| 대표 | 병합, 삽입, Tim | 퀵, 힙, 선택 |
| 다중 키 정렬 | 적합 | 부적합 |
| 추가 비용 | 메모리 또는 성능 | 없음(제자리) |
비교 정렬 vs 비비교 정렬
| 항목 | 비교 정렬 | 비비교 정렬 |
|---|
| 하한 | Omega(n log n) | O(n) 가능 |
| 알고리즘 | 병합, 퀵, 힙 | 계수, 기수, 버킷 |
| 데이터 제약 | 비교 가능하면 모두 | 정수/제한된 범위 |
| 적용 | 범용 | 특수 조건 (정수, 범위 작음) |
외부 정렬 vs 내부 정렬
| 항목 | 외부 정렬 | 내부 정렬 |
|---|
| 데이터 위치 | 디스크 (메모리 초과) | 메모리 내 |
| 방식 | 분할→정렬→병합 | 메모리 내 정렬 |
| I/O | 디스크 I/O 최소화 | 불필요 |
| 적용 | 대용량 DB, 로그 | 일반 배열 정렬 |