정렬 알고리즘
시간 복잡도 비교
| 알고리즘 | 평균 | 최악 | 공간 | 안정성 |
|---|---|---|---|---|
| Bubble Sort | O(n²) | O(n²) | O(1) | 안정 |
| Selection Sort | O(n²) | O(n²) | O(1) | 불안정 |
| Insertion Sort | O(n²) | O(n²) | O(1) | 안정 |
| Merge Sort | O(n log n) | O(n log n) | O(n) | 안정 |
| Quick Sort | O(n log n) | O(n²) | O(log n) | 불안정 |
| Heap Sort | O(n log n) | O(n log n) | O(1) | 불안정 |
| Counting Sort | O(n+k) | O(n+k) | O(k) | 안정 |
| Radix Sort | O(nk) | O(nk) | O(n+k) | 안정 |
Merge Sort
분할 정복. 항상 O(n log n). 연결 리스트 정렬에 유리.
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:]Quick Sort
평균 O(n log n), 최악 O(n²) (피벗이 항상 최솟값/최댓값일 때).
def quick_sort(arr, lo, hi):
if lo < hi:
p = partition(arr, lo, hi)
quick_sort(arr, lo, p - 1)
quick_sort(arr, p + 1, hi)
def partition(arr, lo, hi):
pivot = arr[hi]
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
return i + 1Heap Sort
힙 자료구조 이용. 항상 O(n log n), 추가 메모리 없음.
def heap_sort(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
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
l, r = 2*i+1, 2*i+2
if l < n and arr[l] > arr[largest]: largest = l
if r < n and arr[r] > arr[largest]: largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)