[Heap Sort] 힙 정렬

[Heap Sort] 힙 정렬

힙 정렬은 상당히  효율적인 정렬 알고리즘을 선택 정렬과 유사한 접근 방식을 가졌다.

퀵소트는 대부분의 경우에서 최상위의 성능을 내기 때문에 힙 정렬은 이에 비해 열세이지만,

힙소트는 최악의 경우에도 O(NlogN)을 보장한다.

힙 소트는 두가지 단계로 나누어 볼 수 있다.

1. Heap Tree 구성

2. 다시 정렬을 하면서 Tree 수정

트리를 수정할 때 가장 상위 노드의 값과 가장 마지막 노드의 값을 교환하여

마지막 부터 채워나간다.

하지만 이는 알고리즘을 응용하면 처음부터 채워나갈 수 있지 않을까 싶다.

트리와 배열을 그림으로 그려서 표현하고 싶으나 그거까지는 귀찮....

코드를 구현할 때 참고한 블로그에 그림과 설명이 친절하게 되어있다.

이를 참고해서 공부하면 좋을 것 같다.

#include <stdio.h>
 
int size;
 
void print(int data[])
{
    int i;
 
    for (i = 0; i < size; i++)    {
        printf("%d ", data[i]);
    }
    printf("\n");
}
 
void swap(int *first, int *second)
{
    int temp;
 
    temp = *first;
    *first = *second;
    *second = temp;
}
 
void maketree(int data[], int pos)
{
    int parent = (pos - 1) / 2;
 
    if (data[pos] > data[parent])    {
 
        swap(&data[pos], &data[parent]);
 
        if (pos > 0)    { maketree(data, parent); }
    }
}
 
int maxindex(int data[], int first, int second)
{
    if (data[first] > data[second])    return first;
    return second;
}
 
void modifyTree(int data[], int pos, int last)
{
    int index;
 
    if      (pos * 2 + 2 < last)  { index = maxindex(data, pos * 2 + 1, pos * 2 + 2);}
    else if (pos * 2 + 1 < last)  { index = pos * 2 + 1; }
    else { return; }
    
    if (data[pos] < data[index])    {
        swap(&data[pos], &data[index]);
 
        modifyTree(data, index, last);
    }
}
 
void heapsort(int data[])
{
    int i;
 
    for (i = size - 1; i >= 0; i--)    {
 
        swap(&data[0], &data[i]);
 
        modifyTree(data, 0, i);
    }
}
 
int main(void)
{
 
    int itr;
    int nCount;
 
    scanf("%d", &nCount);
 
    int value, i;
    int data[110];
 
    for (itr = 0; itr < nCount; itr++)    {
        printf("#testcase%d\n", itr + 1);
 
        scanf("%d", &size);
 
        for (i = 0; i < size; i++)    {
            scanf("%d", &value);
 
            data[i] = value;
 
            maketree(data, i);
        }
 
        heapsort(data);
 
        print(data);
    }
 
    return 0;
}

[참고] http://priv.tistory.com/61