힙 정렬에 대하여 알아보기

오늘은 힙 정렬에 대하여 알아보겠습니다.

개요

이 정렬은 힙 자료구조를 이용하여 정렬하는 방법입니다.

힙에서는 항상 큰 원소가 루트 노드, 즉 최상위 노드가 되고, 삭제 연산을 하면 항상 루트 노드의 원소를 삭제하여 반환합니다.

이런 힙의 특징을 이용하여 최대 힙에서 원소의 갯수만큼 삭제 연산을 하면 내림차순을 구현할 수 있고, 최소 힙에서 원소의 갯수만큼 삭제 연산을 하면 오름차순을 구현할 수 있습니다.

힙 정렬은 정렬할 원소들을 입력하여 최대 힙을 구성하게 됩니다.

그리고 힙에 대히여 삭제 연산을 수행하여 얻은 원소를 마지막 자리에 배치하고, 힙을 다시 최대 힙이 되도록 재구성하는 작업을 원소의 갯수만큼 반복하면 모든 오른차순을 구할 수 있습니다.

알고리즘

make(arr[],h,m){
    for(j<-2*h;j<=m;j<-2*j)do{
        if(j<m)then{
            if(arr[j]<arr[j+1])then{
                j<-j+1;
            }
            if(arr[h]>=arr[j])then{
                exit();
            }
            else{
                arr[j/2] <- arr[j];
            }
        }
    }
    arr[j/2] <- arr[h];
}

heap(arr[]){
    n <- arr.length-1;
    for(i<- n/2;i>=1;i<-i+1) do{
        make(arr,i,n);
    }
    for(i<-n-1;i>=1;i<-i-1)do{
        swap(arr[1],arr[i+1]);
        make(arr,1,i);
    }
}

Written on June 9, 2018