[자료구조] 복잡하지만 효율적인 정렬 알고리즘 10-2(힙 정렬)

앞서 소개한 단순한 정렬 알고리즘은 정렬대상의 수가 적은 경우 효울적으로 사용할 수 있지만 정렬 대상의 수가 적지 않은 경우에는 아니다!
그러므로 우리는 이 경우에서도의 만족스러운 결과를 보장하는 알고리즘이 필요하다.

✏️힙 정렬 : 이해와 구현

제목만 복잡하지만..이지! 사실상 앞서 설명한 정렬들이 너무 ~ 간단해서 그에 비해 상대적으로 복잡한 알고리즘이라는뜻이므로 겁먹지 말라는뎅..오히려 기발한 정렬방식이라 나름 재밌을것같다는데....
모르겠다!😂
우선 힙 정렬에 대해 배워보자 !!

힙을 잘 이해했다면 별도로 더 공부할 것이 없는 알고리즘이다.

"힙의 루트 노드에 저장된 값이 가장 커야 한다."
이는 최대 힙의 특징이므로
"힙의 루트 노드에 저장된 값이 정렬순서상 가장 앞선다"라고 말할수 있다.

그럼 다음 예제(소스코드)를 보자

#include <stdio.h>
#include "UsefulHeap.h"

int PriComp(int n1,int n2)
{
    return n2-n1; // 오름차순 정렬을 위한 문장.
}
void HeapSort(int arr[],int n,PriorityComp pc)
{
    Heap heap;
    int i;
    HeapInit(&heap,pc);
    
    //정렬 대상을 가지고 힙을 구성한다.
    for(i=0;i<n;i++)
    {
        HInsert(&heap, arr[i]);
    }
    //순서대로 하나씩 꺼내서 정렬을 완성한다.
    for(i=0;i<n;i++)
    {
        arr[i] = HDelete(&heap);
    }
    
}

int main(void){
    int arr[4] = {3,4,2,1};
    int i;
    
    HeapSort(arr, sizeof(arr)/sizeof(int), PriComp);
    
    for(i=0;i<4;i++)
    {
        printf("%d ",arr[i]);
    }
    printf("\n");
    
    return 0;
}

추가 파일 : UsefulHeap.c,h

힙을 써야하니 당연빠따로 앞서 구현한 유용한 힙의 헤더와 소스파일을 가져왔다.

결과 정렬이 완료된것을 볼 수 있다.

그럼 예제를 분석해보자.

    for(i=0;i<n;i++)
    {
        HInsert(&heap, arr[i]);
    }

데이터를 모두 힙에 넣는다.

    for(i=0;i<n;i++)
    {
        arr[i] = HDelete(&heap);
    }

힙에서 다시 데이터를 꺼낸다.

보다시피.. 정렬의 대상인 데이터들을 그저 힙에 넣었다가 꺼내는 것이 전부이다.
그럼에도 불구하고 정렬이 완성되는 이유는

꺼낼 때 힙의 루트 노드에 저장된 데이터가 반환되기 때문이다 !!! !

힙 정렬 : 성능 평가

언뜻보면 그저 데이터를 전부 넣고 빼서 성능상 이점이 없어 보이지만, 지금까지 소개한 것 중에서는 킹왕짱이다.

힙의 데이터 저장/삭제 시간 복잡도는 로그이엔 이라고 앞서 계산했었다.
따라서 삽입과 삭제를 하나의 연산으로 묶는다면,

정렬대상의 수가 n개라면, 총 n개의 데이터를 삽입 및 삭제 해야하므로 n을 곱해야한다.
그러므로

엔곱하기 로그이엔 이다!

n제곱과 엔곱하기 로그이엔은 큰 차이가 있다 !!!