똑똑한 코드 작성을 위한 실전 알고리즘

176

똑똑한 코드 작성을 위한 실전 알고리즘

그림

5-14

배열을 최대 이진 힙으로 변환하기

[그림

5

-

14

]에서 마지막 행은 최대 이진 힙을 나타낸다 (사실 [그림

4

-

16

]에서 표현한 것과 동

일하다 ). 이제 모든 인덱스 위치를 사용하기 위해 인덱스 위치

1

만큼 오프셋을 가진다. [코드

5

-

9

]의

sort

()

함수는 이제 힙의 마지막 값과 최댓값을 반복적으로 교환([그림

5

-

13

]에서 소

개한 내용 참조 )하면 최종 정렬된 배열에서 해당 값이 위치해야 하는 곳으로 정확하게 이동하

게 된다.

sort

()

가 호출되면 힙 크기는

1

씩 감소하고

sink

()

는

4

장에서 기술한

O

(

log

N

)의

런타임 성능으로 힙 순서 속성을 만족하도록 한다.

5.9

O

(

NlogN

) 알고리즘의 성능 비교하기

서로 다른 정렬 알고리즘(

O

(

N

log

N

)으로 분류된 모든 알고리즘)의 런타임 성능을 어떻게 비

교할까? [표

5

-

1

]은 몇 가지 경험적 결과를 나타낸다. 열의 아래 방향으로 읽어내려가면 문제

레벨 0 레벨 1 레벨 2 레벨 3 레벨 4

정렬할

배열

누적 비교

횟수

177

5

장

정렬

크기가

2

배가 됨에 따른