정렬(Sorting) 알고리즘은 데이터를 정해진 기준(오름차순/내림차순)으로 재배열하는 알고리즘으로, 탐색 연산 성능 최적화의 필수 전제조건입니다.
1. 주요 8대 정렬 알고리즘 비교표
| 알고리즘 | 평균 시간복잡도 | 최악 시간복잡도 | 공간복잡도 | 안정성(Stable) | 핵심 구현 특징 |
|---|---|---|---|---|---|
| 선택 정렬 | $O(N^2)$ | $O(N^2)$ | $O(1)$ | X | 최솟값 찾아 맨 앞과 교환 |
| 삽입 정렬 | $O(N^2)$ | $O(N^2)$ | $O(1)$ | O | 정렬된 구간에 요소 삽입 |
| 쉘 정렬 | $O(N^{1.3})$ | $O(N^2)$ | $O(1)$ | X | 간격(Gap)을 줄여가며 삽입 정렬 |
| 힙 정렬 | $O(N log N)$ | $O(N log N)$ | $O(1)$ | X | 이진 힙 구조 활용 |
| 병합 정렬 | $O(N log N)$ | $O(N log N)$ | $O(N)$ | O | 분할 정복 + 추가 배열 병합 |
| 퀵 정렬 | $O(N log N)$ | $O(N^2)$ | $O(log N)$ | X | 피봇 기반 2분할 재귀 정렬 |
| 기수 정렬 (LSD) | $O(dN)$ | $O(dN)$ | $O(N+k)$ | O | 자릿수 비교 (비비교 정렬) |
2. 쉘 정렬(Shell Sort)과 병합 정렬(Merge Sort) 코드
# 1. 쉘 정렬 (Shell Sort)
def shell_sort(a):
h = len(a) // 2
while h >= 1:
for i in range(h, len(a)):
j = i
while j >= h and a[j - h] > a[j]:
a[j], a[j - h] = a[j - h], a[j]
j -= h
h //= 2
# 2. 병합 정렬 (Merge Sort)
def merge_sort(a):
if len(a) <= 1:
return a
mid = len(a) // 2
left = merge_sort(a[:mid])
right = merge_sort(a[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
3. 파이썬 기본 정렬: Timsort
파이썬의 list.sort()와 sorted()는 Timsort 알고리즘을 사용합니다.
- Timsort: 삽입 정렬과 병합 정렬을 결합한 하이브리드 정렬 알고리즘입니다.
- 작은 덩어리(Run, 32~64 크기)에는 삽입 정렬을 적용하고, 이들을 병합 정렬 방식으로 합칩니다.
- 최선의 경우 $O(N)$, 최악의 경우 $O(N log N)$을 보장하며 정렬 안정성(Stable)을 유지합니다.
4. 자주 묻는 질문 (Q&A)
Q. 퀵 정렬이 병합 정렬보다 평균적으로 빠른 이유는 무엇인가요? A. 퀵 정렬은 추가 배열을 할당하지 않는 제자리 정렬(In-place)이며, 참조 지역성(Locality of Reference)이 뛰어나 CPU 캐시 히트율이 높기 때문입니다.