[알고리즘] 힙 정렬(heap sort)

자료구조인 힙(heap)을 이용한 정렬 알고리즘

• Heap을 구성한 후 원소들을 다 삽입하고 하나씩 빼면서 배열의 앞에서부터 채워넣는다.

#define N 6

int data[N] = {40, 6, 1, 9, 3, 5};
int h[N + 5];
int cnt;

heapSort(0, N - 1);

void swap(int i, int j)
{
    int t = h[i];
    h[i] = h[j];
    h[j] = t;
}

void upHeapify(int index)
{
    if (index == 1)
        return;
    if (h[index] < h[index / 2])
    {
        swap(index, index / 2);
        upHeapify(index / 2);
    }
}

void insert(int data)
{
    h[++cnt] = data;
    upHeapify(cnt);
}

void downHeapify(int index)
{
    int temp;

    if (index * 2 > cnt)
        return;

    if (index * 2 + 1 <= cnt)
    {
        if (j[index * 2] < h[index * 2 + 1])
            temp = index * 2;
        else
            temp = index * 2 + 1;
    }
    else
        temp = index * 2;

    if (h[temp] < h[index])
    {
        swap(index, temp);
        downHeapify(temp);
    }
}

void pop(void)
{
    h[1] = h[cnt--];
    downHeapify(1);
}

int top(void)
{
    return h[1];
}

void heapSort(int st, int ed)
{
    int i;
    for (i = st; i <= ed; i++)
        insert(data[i]);
    for (i = st; i <= ed; i++)
    {
        data[i] = top();
        pop();
    }
}

• 시간복잡도 : O(Nlog(N))
• 공간복잡도 : O(Nlog(N))