7-2 Heap sort 구현 및 big-O

힙소트의 경우, big-O는 O(NlogN) 입니다.

 

왜 NlogN일까요?

 

Heapify 해주는데 logN, 정렬하는데 N, 곱해서 NlogN입니다.

 

자, 얘를 한번 구현해보겠습니다.

 

그 전에 파이썬 반복문 하나 보고 가겠습니다 :)

 

for i in range(10, -1, -1) :
    print(i)

 

10
9
8
7
6
5
4
3
2
1
0

 

for i in range(10, -1, -2) :
    print(i)

10
8
6
4
2
0

 

for i in range(10, -2, -1) :
    print(i)

 

10
9
8
7
6
5
4
3
2
1
0
-1

 

--

 

자, 일단 파이썬 반복문 어떻게 동작되는지 확인했습니다.

 

heapify와, heap sort를 코딩으로 구현해봤습니다.

 

 

 

 

 

 

물론 이것도 코드만으로 머릿속에서 다 동작되면 엄청나게 훌륭하신 분이시구요

 

저는 로그를 안 찍어보면 상상이 잘 가지 않아서 로그를 찍어봤습니다.

 

만약 로그를 찍으면은

 

 

 

 

아래와 같이 출력물이 나오는 것을 확인하실 수 있습니다.

 

----

 

heapSort
heapSort_i_before : 5

heapify
list: [4, 10, 3, 5, 1] n : 5 i : 5
nothing
heapSort_i_before : 4

heapify
list: [4, 10, 3, 5, 1] n : 5 i : 4
nothing
heapSort_i_before : 3

heapify
list: [4, 10, 3, 5, 1] n : 5 i : 3
nothing
heapSort_i_before : 2

heapify
list: [4, 10, 3, 5, 1] n : 5 i : 2
nothing
heapSort_i_before : 1

heapify
list: [4, 10, 3, 5, 1] n : 5 i : 1
nothing
heapSort_i_before : 0

heapify
list: [4, 10, 3, 5, 1] n : 5 i : 0
왼쪽 애가 더 큽니다.
list[i] < list[left] : 4 10
Swap
list : [4, 10, 3, 5, 1] n : 5 root_largest: 1

heapify
list: [10, 4, 3, 5, 1] n : 5 i : 1
왼쪽 애가 더 큽니다.
list[i] < list[left] : 4 5
Swap
list : [10, 4, 3, 5, 1] n : 5 root_largest: 3

heapify
list: [10, 5, 3, 4, 1] n : 5 i : 3
nothing
nothing
nothing
heapSort_i_after : 4

heapify
list: [1, 5, 3, 4, 10] n : 4 i : 0
왼쪽 애가 더 큽니다.
list[i] < list[left] : 1 5
Swap
list : [1, 5, 3, 4, 10] n : 4 root_largest: 1

heapify
list: [5, 1, 3, 4, 10] n : 4 i : 1
왼쪽 애가 더 큽니다.
list[i] < list[left] : 1 4
Swap
list : [5, 1, 3, 4, 10] n : 4 root_largest: 3

heapify
list: [5, 4, 3, 1, 10] n : 4 i : 3
nothing
nothing
nothing
heapSort_i_after : 3

heapify
list: [1, 4, 3, 5, 10] n : 3 i : 0
왼쪽 애가 더 큽니다.
list[i] < list[left] : 1 4
Swap
list : [1, 4, 3, 5, 10] n : 3 root_largest: 1

heapify
list: [4, 1, 3, 5, 10] n : 3 i : 1
nothing
nothing
heapSort_i_after : 2

heapify
list: [3, 1, 4, 5, 10] n : 2 i : 0
nothing
heapSort_i_after : 1

heapify
list: [1, 3, 4, 5, 10] n : 1 i : 0
nothing
result :  [1, 3, 4, 5, 10]

 

----

 

그렇다면 힙소트의 시간복잡도는 어떻게 될까요??

 

트리 형태로 정비하는 것(heapify)가 log n 이고, 이 것을 n개 갯수만큼 진행하기 때문에

 

시간복잡도는 O(NlogN)입니다.