힙 정렬
힙 정렬은 힙 자료구조를 기반으로 동작하는 알고리즘 입니다.
힙 정렬은 평균 시간 복잡도와 최악 시간 복잡도 모두 \(\theta(nlogn)\)으로 빠른 정렬 알고리즘입니다.
구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# 힙 구성
def heapify(array, n, i):
largest = i # root node
left = 2 * i + 1
right = 2 * i + 2
# left > root
if left < n and array[i] < array[left]:
largest = left
# right > root or largest child
if right < n and array[largest] < array[right]:
largest = right
if largest != i:
array[i], array[largest] = array[largest], array[i]
heapify(array, n, largest)
# 힙 정렬
array = [5, 3, 7, 1, 4, 2, 6, 8]
def heap_sort(array):
n = len(array)
for i in range(n // 2 - 1, -1, -1):
heapify(array, n, i)
for i in range(n - 1, 0, -1):
array[i], array[0] = array[0], array[i]
heapify(array, i, 0)
return array
print(heap_sort(array))
시간 복잡도
힙 정렬은 평균 시간 복잡도와 최악 시간 복잡도 모두 \(\theta(nlogn)\)으로 빠른 정렬 알고리즘입니다.