[Algorithm] 힙 정렬 (Heap Sort)

Heap Sort

힙 정렬은 힙을 사용해 데이터를 정렬하는 알고리즘이다.

힙의 루트 노드에서 지속적으로 값을 꺼내면 특정한 순서로 정렬할 수 있다.

 

힙 자료구조를 모른다면 다음 글을 참고하자.

2025.01.13 - [Programming/Data Structure] - [Data Structure] 힙 트리

오름차순으로 정렬 (Ascending Order)

\내림차순으로 정렬 (Descending Order) 1

내림차순으로 정렬 (Descending Order) 2

코드

#include <iostream>
#include "../Chapter5/5.6/MaxHeap.hpp"

void Print(int* arr)
{
    for (int i = 0; i < 10; i++)
    {
        std::cout << arr[i] << " ";
    }
    std::cout << "\n";
}

int* HeapSort(int* arr)
{
    int* result = new int[10];

    MaxHeap<int> heap;
    
    for (int i = 0; i < 10; i++)
        heap.Push(arr[i]);

    for (int i = 9; i >= 0; i--)
    {
        result[i] = heap.Top();
        heap.Pop();
    }

    return result;
}

int main()
{
    std::cin.tie(0);
    std::ios::sync_with_stdio(0);

    int arr[10] = {8, 31, 48, 73, 3, 65, 20, 29, 11, 15};

    Print(arr);
    int* result = HeapSort(arr);
    Print(result);
}

시간 복잡도

n개의 모든 원소를 뽑을 때마다 힙으로 만드는 Heapify가 O(logn)이 필요하므로 힙 정렬의 시간 복잡도는 O(nlogn)이다.