[알고리즘] 힙 정렬 (Heap Sort)

힙 정렬

선택 정렬을 응용한 알고리즘인 힙 정렬은 힙의 특성을 이용하여 정렬을 수행한다.

힙 상태에서 루트를 꺼내고 다시 힙 상태 유지를 반복

 

 

코드

 //힙 정렬
 
 #define swap(type, x, y) do { type t = x; x = y; y = t;} while(0)

 // a[left] ~ a[right] 를 힙으로 만드는 함수. a[left] 이외에는 모두 힙 상태라고 가정.
 static void downheap (int a[], int left, int right) {
     int temp = a[left]; // 루트
     int child;
     int parent;
     
     
     // 이 인덱스를 기준으로 다음 인덱스부터는 리프노드임 -> (Right-1)/2
     // (Right-1)/2 + 1 보다 작아야 리프노드가 아닌것 = (Right +1)/2보다 작아야 리프노드가 아닌것
     for(parent = left; parent < (right + 1) / 2; parent = child) {
         int cl = parent * 2 + 1; // 왼쪽 자식
         int cr = cl + 1; // 오른쪽 자식
         
         // 일단 리프가 아니라는것은 아니까 cr이 없으면 바로 cl로 처리.
         child = (cr <= right && a[cr] > a[cl]) ? cr : cl; // 차일드 둘 중 큰 값 선택
         
         if(temp >= a[child]) // 이미 힙 상태인 경우 (부모보다 자식의 값이 이미 작음)
             break;
         
         a[parent] = a[child];
     }
     a[parent] = temp; // 밀어내기 후 채우기.
 }

 // 힙 정렬 함수
 void heap_sort(int a[], int n) {
     int i;
     
     // 리프노드가 아닌 노드부터 루트노드까지 downheap 진행하여 힙으로 만들어줌. 근데 생각해보니 n은 크기이므로 리프노드가 아닌 노드는 (n - 1)/2가 아니라 (n - 2)/2부터인데 책의 예제에선 (n - 1)/2로 해서 쓸모없는 작업 하나 더 하더라. (+이상해서 디버깅으로 직접 확인함)
     for(i = (n - 2) / 2; i >= 0; i--) {
         downheap(a, i, n - 1);
     }
     // i가 0이되면 종료(힙정렬 end 조건임)
     for(i = n - 1; i > 0; i--) {
         swap(int, a[0], a[i]);
         downheap(a, 0, i - 1);
     }
 }

 

downheap 함수 

배열 a 가운데 a[left] ~ a[right]의 요소를 힙으로 만드는 함수. a[left] 이외에는 모두 힙 상태라고 가정하고 a[left]를 아랫부분의 알맞은 위치로 옮겨 힙 상태를 만든다. 

heapsort 함수 

요소의 개수가 n인 배열 a를 힙정렬한다.
1. downheap을 사용해 배열 a를 힙으로 만든다.
(배열로 힙 만들기)
2. 루트에 있는 가장 큰 값을 빼내어 배열 마지막 요소와 바꾸고 배열의 나머지 부분을 다시 힙으로 만드는 과정을 반복하여 정렬 수행.
(힙 정렬 알고리즘 by 배열) 

힙 정렬은 단순 선택 정렬을 응용한 알고리즘이다. 그리고 역시나 안정적이지 않은 정렬이다. 

힙 정렬의 시간복잡도 : O(n log n)