정렬 알고리즘 한눈에 비교
정렬 알고리즘 8가지를 표 하나로 비교합니다. 각 알고리즘의 자세한 동작과 Python 코드는 이름을 눌러 보세요.
비교 정렬 6가지
값끼리 "누가 더 크냐"를 비교하면서 정렬하는 방법입니다.
| 정렬 알고리즘 | 평균 시간복잡도 | 최악 시간복잡도 | 안정 정렬 | 특징 |
|---|---|---|---|---|
| 삽입 정렬 (Insertion) | O(N²) | O(N²) | O (안정) | 대부분 정렬되어 있을 때 매우 빠름 |
| 버블 정렬 (Bubble) | O(N²) | O(N²) | O (안정) | 구현이 가장 간단하지만 성능이 떨어짐 |
| 선택 정렬 (Selection) | O(N²) | O(N²) | X (불안정) | 교환 횟수가 적지만 항상 일정한 시간 소요 |
| 병합 정렬 (Merge) | O(N log N) | O(N log N) | O (안정) | 항상 일정한 성능을 보장하나 추가 메모리 필요 |
| 퀵 정렬 (Quick) | O(N log N) | O(N²) | X (불안정) | 피벗 선택에 따라 최악의 경우가 발생할 수 있음 |
| 힙 정렬 (Heap) | O(N log N) | O(N log N) | X (불안정) | 추가 메모리가 필요 없는 효율적인 정렬 |
비교하지 않는 정렬 2가지
값을 서로 비교하지 않고, 자릿수나 개수를 세서 제자리를 찾아 주는 방법입니다. 조건이 맞으면 O(N log N)보다 빠릅니다.
| 정렬 알고리즘 | 시간복잡도 | 안정 정렬 | 특징 |
|---|---|---|---|
| 기수 정렬 (Radix) | O(d × (N + k)) | O (안정) | 자릿수(d)별로 나눠 담기를 반복. 정수·길이가 같은 문자열에 적합 |
| 계수 정렬 (Counting) | O(N + k) | O (안정) | 값마다 몇 번 나왔는지 세기. 값의 범위(k)가 작을 때만 유리 |
용어 정리
- 평균 시간복잡도: 입력 가능한 모든 데이터가 골고루 들어온다고 가정했을 때 걸리는 평균 연산 횟수 (= 일반 성능)
- 최악 시간복잡도: 가장 불리한 데이터 패턴이 들어왔을 때 걸리는 최대 연산 횟수 (= 보장되는 최악 성능)
- 안정 정렬: 정렬 기준이 같은 중복 데이터가 여러 개일 때, 정렬 전의 상대 순서가 정렬 후에도 유지됨
- 예) 상품을 1차로 추천순 정렬한 뒤 다시 2차로 가격순 정렬하면, 가격이 같은 상품끼리는 추천순 순서가 그대로 유지됨
- 제자리 정렬 (in-place): 입력 배열 말고 추가 메모리를 거의 쓰지 않는 정렬 (거품·선택·삽입·힙·퀵)
O(N²), O(N log N)이 얼마나 차이 나는지는 시간 복잡도 글에 정리해 두었습니다.
직접 손으로 정리한 노트: 정렬 알고리즘 비교와 용어
정리
| 개념 | 비전공자 버전 요약 |
|---|---|
| O(N²) 정렬 | 거품·선택·삽입. 쉽지만 데이터가 많으면 느림 |
| O(N log N) 정렬 | 병합·퀵·힙. 실무에서 쓰는 빠른 정렬 |
| 비교 안 하는 정렬 | 기수·계수. 값의 범위가 좁으면 가장 빠름 |
| 안정 정렬 | 같은 값끼리 원래 순서가 유지되는 정렬 |