[C언어 알고리즘] 3.5.2 힙 정렬 알고리즘 성능 분석

[C언어 알고리즘] 3.5.2 힙 정렬 알고리즘 성능 분석

---

 

이번에는 힙 정렬 알고리즘의 수행 속도를 계산해 보기로 해요.

 

힙 정렬(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)성능을 보장하는 정렬 방식입니다.