이번에는 힙 정렬 알고리즘의 수행 속도를 계산해 보기로 해요.
힙 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
초기 힙 구성
루트와 맨 마지막 자손 교환
n을 1 감소
반복(n: n->1)
힙 구성
루트와 맨 마지막 자손 교환
n을 1 감소
힙 정렬 알고리즘 수행 속도는 초기 힙 구성과 힙 구성을 n-1번 수행하는 비용의 합입니다.
수행 속도 = 초기 힙 구성 속도 + 힙 구성 속도 * (n-1)
초기 힙 구성(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
반복(i:1->n)
j:=1
반복(j>0)
pa:=PARENT(j)
조건: compare(base[j], base[pa])이 0보다 크면
base[j], base[pa] 교환
j: = pa
아니면
내부 루프 탈출
먼저 초기 힙 구성하는 시간을 계산해 보기로 해요.
초기 힙 구성은 내부 반복문을 n번 수행합니다. 그리고 내부 반복문은 트리 높이에 따라 비용이 차이가 생기는데 맨 마지막 자료를 구성할 때 걸리는 시간이 최악입니다. 그리고 맨 마지막 자료를 구성할 때 부모와 비교하면서 교환하기 때문에 최악일 때 비교와 교환을 트리의 높이만큼 진행합니다. 따라서 logN보다 작습니다. 따라서 초기 힙 구성 비용은 최악일 때도 NlogN보다 작습니다.
초기 힙 구성 비용 ≤ NlogN
힙 구성(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
반복
lc:= LCHILD(me)
rc:= RCHILD(me)
자식이 없으면
탈출
조건 왼쪽 자식만 있을 때
조건 compare(base[me],base[lc])>0일 때
base[me], base[lc] 교환
탈출
bc := 왼쪽 자식과 오른쪽 자식 중에 자료가 큰 값의 인덱스
조건 compare(base[bc],base[me])>0일 때
base[bc],base[me] 교환
아니면
탈출
힙 구성은 N-1 번 수행합니다. 그리고 힙 구성에 걸리는 비용은 트리의 높이가 제일 높을 때 최악이 나옵니다. 자식과 비교하면서 교환하므로 logN에 비례합니다. 따라서 전체 힙 구성에 걸리는 비용의 합은 NlogN보다 작습니다.
전체 힙 구성에 걸리는 비용의 합 ≤ Nlog(N)
따라서 힙 정렬에 드는 비용은 초기 힙 구성 비용(Nlog(N)보다 작음)과 전체 힙 구성에 걸리는 비용(NlogN보다 작음)이므로 2NlogN보다 작다고 할 수 있습니다. 따라서 빅 오 점근식 표기법으로 표현한다면 상수를 제거하여 O(NlogN)이라고 말할 수 있습니다.
일반적으로 퀵 정렬이 가장 빠르다고 알려졌지만 선택한 피벗의 성질에 따라 다른 성능을 보이기 때문에 실제로 가장 빠른 것은 아닙니다. 오히려 힙 정렬은 자료의 성질과 관계없이 안정적으로 O(NlogN)을 보장합니다. 이 외에도 다룰 병합 정렬과 기수 정렬도 O(NlogN)성능을 보장하는 정렬 방식입니다.