[Programming/Algorithm] 힙 정렬(Heap Sort)

힙 정렬은 힙의 다음 특성을 활용하여 정렬하는 알고리즘이다.

힙의 루트 노드에 저장된 값이 가장 커야 한다.

이는 '최대 힙(max heap)'의 특징이다. 이것을 다음과 같은 특징을 갖도록 힙을 구성할 수도 있다.

힙의 루트 노드에 저장된 값이 정렬순서상 가장 앞선다.

---

2021/03/07 - [Programming/Algorithm] - [Programming/Algorithm] 우선순위 큐와 Heap 자료구조

[Programming/Algorithm] 우선순위 큐와 Heap 자료구조

#include <iostream>
#include "SimpleHeap.h"

using std::cout;
using std::cin;
using std::endl;

int PriComp(int n1, int n2) {
    return n2 - n1;
}

void HeapSort(int arr[], int n, PriorityComp pc) {
    Heap heap;
    HeapInit(&heap, pc);

    // 정렬 대상을 가지고 힙을 구성한다.
    for (int i = 0; i < n; i++) {
        HInsert(&heap, arr[i]);
    }

    // 순서대로 하나씩 꺼내서 정렬을 완성한다.
    for (int i = 0; i < n; i++) {
        arr[i] = HDelete(&heap);
    }
}

int main() {
    int arr[4] = { 3, 4, 2, 1 };

    HeapSort(arr, sizeof(arr) / sizeof(int), PriComp);

    for (int i = 0; i < 4; i++) {
        cout << arr[i] << ' ';
    }
    cout << endl;

    return 0;
}


/* 결과

1 2 3 4

*/

위의 예제를 보다시피 정렬의 대상인 데이터들을 힙에 넣었다가 꺼내는 것이 전부이다. 그럼에도 불구하고 정렬이 완료되는 이유는, 꺼낼 때 힙의 루트 노드에 저장된 데이터가 반환되기 때문이다.

힙은 저장의 목적 이외에 정렬의 도구로도 사용이 될 수 있다. 그리고 그 성능은 만족스러운 편이다.

---

힙 정렬(Heap Sort) : 성능평가

언뜻 보면 저장된 데이터를 죄다 힙에 넣었다가 다시 꺼내기 때문에 성능상 이점이 별로 없어 보이지만, 힙 정렬은 버블정렬, 선택정렬, 삽입정렬 중 가장 좋은 성능을 보이는 알고리즘이다.

• 힙의 데이터 저장 시간 복잡도 : O(log2n)
• 힙의 데이터 삭제 시간 복잡도 : O(log2n)

따라서 삽입과 삭제를 하나의 연산으로 묶는다면, 이 연산에 대한 시간 복잡도는 다음과 같이 결론 내릴 수 있다.

• O(2log2n)

하지만 숫자 2는 빅-오에서 무시할만한 수준이므로 삽입과 삭제를 하나의 연산으로 묶는다 해도, 이 연산에 대한 시간 복잡도는 여전히 다음과 같다.

• O(log2n)

그럼 정렬과정에 대한 시간 복잡도는 어떻게 될까? 정렬대상의 수가 n개라면, 총 n개의 데이터를 삽입 및 삭제해야 하므로 위의 빅-오에 n을 곱해야 한다.

• O(nlog2n)

nlog2n과 n의 제곱에는 별 차이가 없다고 생각할지 모른다. 하지만 n에 몇몇 숫자만 넣어도 그 차이를 바로 알 수 있다.

n	10	100	1,000	3,000	5,000
n의 제곱	100	10,000	1,000,000	9,000,000	25,000,000
nlog2n	66	664	19,931	34,652	61,438

위의 표에서 보이듯이, nlog2n과 n의 제곱에는 큰 차이가 있다. 참고로 말하자면 O(n의 제곱)의 성능을 보이는 알고리즘을 O(nlog2n)의 성능을 보이도록 개선한다면, 이는 낮은 성능으로 인하여 현실적으로 활용하기 어려운 알고리즘을 활용이 가능한 가능한 수준으로 개선한 결과로도 평가 받을 수 있다.