정렬 알고리즘(Sorting Algorithm)은 데이터를 일정한 순서로 나열하는 알고리즘이다. 검색 효율화(이진 탐색), 데이터 분석, 데이터베이스 등 모든 컴퓨팅 분야의 핵심 기반이다.
주요 정렬 알고리즘 비교
| 알고리즘 | 평균 | 최악 | 메모리 | 안정성 |
|---|
| 버블 정렬 | O(n²) | O(n²) | O(1) | ✓ |
| 선택 정렬 | O(n²) | O(n²) | O(1) | ✗ |
| 삽입 정렬 | O(n²) | O(n²) | O(1) | ✓ |
| 퀵 정렬 | O(n log n) | O(n²) | O(log n) | ✗ |
| 병합 정렬 | O(n log n) | O(n log n) | O(n) | ✓ |
| 힙 정렬 | O(n log n) | O(n log n) | O(1) | ✗ |
| 기수 정렬 | O(nk) | O(nk) | O(n+k) | ✓ |
안정 정렬: 같은 값의 원소가 정렬 후에도 원래 순서를 유지하는 것.
비교 기반 vs 비비교 기반 정렬
| 분류 | 알고리즘 | 하한 복잡도 | 특징 |
|---|
| 비교 기반 | 퀵, 병합, 힙 | Ω(n log n) | 범용, 어떤 데이터도 가능 |
| 비비교 기반 | 계수, 기수, 버킷 | O(n+k) | 특수 조건 필요, 더 빠름 가능 |
계수 정렬 (Counting Sort)
값의 빈도를 세어 정렬. 범위가 한정된 정수에서 O(n+k) 달성.
arr = [4, 2, 2, 8, 3, 3, 1] (범위: 1~8)
count = [0, 1, 2, 2, 1, 0, 0, 0, 1] (각 값의 개수)
결과 = [1, 2, 2, 3, 3, 4, 8]
- •시간: O(n+k) (k = 값의 범위)
- •공간: O(k)
- •제약: 음수, 실수, 문자열 불가
기수 정렬 (Radix Sort)
자릿수(digit)별로 반복 정렬. 계수 정렬을 자릿수마다 적용.
arr = [170, 45, 75, 90, 802, 24, 2, 66]
1의 자리 정렬: [170, 90, 802, 2, 24, 45, 75, 66]
10의 자리 정렬: [802, 2, 24, 45, 66, 170, 75, 90]
100의 자리 정렬: [2, 24, 45, 66, 75, 90, 170, 802]
- •시간: O(d × (n+k)) (d = 최대 자릿수)
- •활용: 정수, 문자열의 대용량 정렬
퀵 정렬 (Quick Sort)
실무에서 가장 많이 쓰이는 정렬. 분할 정복 방식으로 피벗을 기준으로 분할.
python
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
print(quicksort([3, 6, 8, 10, 1, 2, 1]))
# [1, 1, 2, 3, 6, 8, 10]
동작 과정:
[3, 6, 8, 10, 1, 2, 1] pivot=8
left=[3,6,1,2,1] middle=[8] right=[10]
→ 재귀 정렬 후 합침
병합 정렬 (Merge Sort)
안정 정렬, 항상 O(n log n) 보장. 분할 정복 방식.
python
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
return result + left[i:] + right[j:]
힙 정렬 (Heap Sort)
힙 자료구조를 이용한 정렬. O(n log n), 추가 메모리 불필요.
python
import heapq
def heap_sort(arr):
heapq.heapify(arr) # 힙으로 변환 O(n)
return [heapq.heappop(arr) for _ in range(len(arr))] # O(n log n)
삽입 정렬 (Insertion Sort)
거의 정렬된 데이터에 O(n)에 가까운 성능. 소규모 데이터에 유리.
python
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
언어 내장 정렬의 알고리즘
| 언어 | 알고리즘 | 특징 |
|---|
| Python | Timsort | 병합+삽입 정렬 결합, 안정 정렬 |
| Java | Dual-Pivot QuickSort | 원시 타입, 객체는 Timsort |
| C++ std::sort | IntroSort | 퀵+힙+삽입 정렬 결합 |
| JavaScript | Timsort | V8 엔진 기준 |
관련 개념
- •이진 탐색 — 정렬된 배열 전제
- •힙 — 힙 정렬의 기반 자료구조
- •동적 프로그래밍 — 알고리즘 설계 패러다임
- •이진 트리 — 트리 기반 정렬(BST, 힙 트리)
참고문헌
- •Cormen et al. Introduction to Algorithms — Chapter 6, 7, 8
- •Sedgewick & Wayne. Algorithms, 4th Edition
