[Daily morning study] 정렬 알고리즘 비교 (Quick Sort, Merge Sort, Heap Sort)
in Daily morning study / DSA
#daily morning study
왜 정렬 알고리즘을 비교해야 하나
정렬은 알고리즘에서 가장 기본이 되는 연산 중 하나다. 언어 표준 라이브러리의 sort 함수가 내부적으로 어떤 알고리즘을 쓰는지, 왜 그 선택을 했는지를 이해하면 성능 문제를 마주쳤을 때 더 잘 대응할 수 있다.
Quick Sort
동작 원리
피벗(pivot)을 하나 고르고, 피벗보다 작은 값들은 왼쪽, 큰 값들은 오른쪽으로 분리(파티셔닝)한 뒤 재귀적으로 반복한다.
def quick_sort(arr, low, high):
if low < high:
pivot_idx = partition(arr, low, high)
quick_sort(arr, low, pivot_idx - 1)
quick_sort(arr, pivot_idx + 1, high)
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
시간 복잡도
| 케이스 | 복잡도 |
|---|---|
| 평균 | O(n log n) |
| 최선 | O(n log n) |
| 최악 | O(n²) |
최악은 이미 정렬된 배열에서 피벗을 항상 최솟값이나 최댓값으로 고를 때 발생한다. 이를 피하기 위해 랜덤 피벗 선택이나 median-of-three 전략을 쓴다.
특징
- In-place: 추가 메모리가 O(log n) 스택 공간뿐이다.
- Not stable: 같은 값의 원소들이 원래 순서를 보장하지 않는다.
- 캐시 친화적: 연속된 메모리를 순차 접근하므로 실제 성능이 이론보다 훨씬 좋다.
- C의
qsort, Java의Arrays.sort(int[]), Python의timsort(실질적으로 merge sort 기반이지만 작은 파티션엔 insertion sort 사용)가 퀵 정렬 계열을 활용한다.
Merge Sort
동작 원리
분할 정복(divide and conquer) 방식. 배열을 절반씩 쪼개다가 원소가 1개가 되면, 올라오면서 두 정렬된 배열을 합병(merge)한다.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[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
시간 복잡도
| 케이스 | 복잡도 |
|---|---|
| 평균 | O(n log n) |
| 최선 | O(n log n) |
| 최악 | O(n log n) |
항상 O(n log n)을 보장한다.
특징
- Stable: 같은 값의 원소 순서를 보장한다. 객체를 여러 키로 정렬할 때 중요하다.
- Not in-place: 합병 과정에서 O(n) 추가 메모리가 필요하다.
- 외부 정렬(External Sort)에 적합: 디스크에 저장된 대용량 데이터를 정렬할 때 병합 정렬 방식이 기본이다. 메모리에 다 올릴 수 없어도 청크 단위로 정렬 후 합칠 수 있다.
- Java의
Collections.sort(), Python의timsort는 merge sort 기반이다. (객체 정렬에서 stability가 필요하기 때문)
Heap Sort
동작 원리
최대 힙(Max Heap)을 구성한 뒤, 루트(최댓값)를 배열 끝과 교환하고 힙 크기를 줄여가며 반복한다.
def heap_sort(arr):
n = len(arr)
# Build max heap
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# Extract elements one by one
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
시간 복잡도
| 케이스 | 복잡도 |
|---|---|
| 평균 | O(n log n) |
| 최선 | O(n log n) |
| 최악 | O(n log n) |
특징
- In-place: 추가 메모리가 O(1)이다.
- Not stable: 힙 구성 과정에서 순서가 뒤바뀐다.
- 캐시 비친화적: 힙 구조 특성상 메모리 접근 패턴이 불규칙하다. 이론 복잡도는 quick sort와 같지만 실제 성능은 보통 더 느리다.
- 메모리가 극도로 제한된 환경이나 최악 케이스를 반드시 O(n log n)으로 보장해야 할 때 사용한다.
세 알고리즘 한눈에 비교
| 항목 | Quick Sort | Merge Sort | Heap Sort |
|---|---|---|---|
| 평균 시간 복잡도 | O(n log n) | O(n log n) | O(n log n) |
| 최악 시간 복잡도 | O(n²) | O(n log n) | O(n log n) |
| 공간 복잡도 | O(log n) | O(n) | O(1) |
| Stable | No | Yes | No |
| 캐시 친화성 | 높음 | 중간 | 낮음 |
| 실제 성능 | 가장 빠름 | 중간 | 느린 편 |
| 주 사용처 | 일반 목적 | 객체 정렬, 외부 정렬 | 우선순위 큐, 제한된 메모리 |
Introsort — 실전의 선택
대부분의 표준 라이브러리 정렬은 단일 알고리즘을 쓰지 않는다. C++의 std::sort는 Introsort를 사용한다.
- 기본은 Quick Sort (캐시 친화적, 빠름)
- 재귀 깊이가
2 * log(n)을 초과하면 → Heap Sort로 전환 (최악 케이스 O(n²) 방지) - 원소 수가 작으면(보통 16 이하) → Insertion Sort로 전환 (오버헤드가 없어서 소규모에서 빠름)
이렇게 세 알고리즘의 장점만 조합해서 평균도 빠르고 최악도 O(n log n)을 보장한다.
Timsort — Python, Java의 선택
Python과 Java(객체 배열)는 Timsort를 사용한다.
- 실제 데이터는 부분적으로 정렬된 경우가 많다는 관찰에서 출발
- 이미 정렬된 run(연속 구간)을 찾아내고
- Merge Sort로 run들을 합병
- 작은 run은 Insertion Sort로 확장
Timsort의 특징:
- Stable (객체 정렬에 필요)
- 이미 정렬된 데이터에서 O(n) 성능
- 최악 O(n log n) 보장
언제 어떤 걸 써야 하나
- 일반 목적: 언어의 기본 sort 함수를 쓰면 된다. 대부분 Introsort나 Timsort 기반이다.
- stability가 필요: Merge Sort 또는 Timsort.
- 메모리 제한이 심하고 최악 보장도 필요: Heap Sort.
- 알고리즘 문제에서 커스텀 정렬이 필요: Quick Sort를 직접 구현하거나 언어 내장 sort에 comparator를 넘기면 된다.
- 외부 정렬 (디스크 데이터): Merge Sort 계열.
