[알고리즘] 정렬 알고리즘 - 힙 정렬 Heap Sort - 부연

 

힙 정렬 (Heap Sort) 알고리즘 : 

'부모의 값이 자식의 값보다 항상 크다 or 작다' 를 만족하는 완전이진트리 힙 의 특성을 이용하여 정렬 수행. 

선택 정렬 을 응용한 알고리즘

 

 

 

 

 

메소드 swap() : a[idx1] 과 a[idx2] 를 교환

매개변수 : int[] a, int idx1, int idx2

 

메소드 donwHeap() : 배열 a의 index left 부터 right 까지 요소를 힙으로 만든다

매개변수 : int[] a, int left, int right

메소드 heapSort() : 길이가 n인 배열 a를 힙 정렬

매개변수 : int[] a, int n

 

- 힙 정렬 :

java

닫기 줄바꿈

void swap(int[]a, int idx1, int idx2) {
‌int t = a[idx1];
‌a[idx1] = a[idx2];
‌a[idx2] = t;
}

void downHeap(int[] a, int left, int right) {
‌int temp = a[left];
‌int child;
‌int parent;
‌
‌for(parent = left; parent <(right+1)/2; parent = child) {
‌‌int cl = parent * 2 +1;
‌‌int cr = cl + 1;
‌‌child = (cr <= right && a[cr] > a[cl]) ? cr : cl;
‌‌if(temp >= a[child])
‌‌‌break;
‌‌a[parent] = a[child];
‌}
‌a[parent] = temp;
}
‌
void heapSort(int[] a, int n) {
‌for(int i = (n-1)/2; i >= 0; i--)
‌‌downHeap(a, i, n - 1);
‌
‌for(int i = n-1; i > 0; i--) {
‌‌swap(a, 0, i);
‌‌downHeap(a, 0, i-1);
‌}
}

 

 

 

 

힙 정렬 Heap Sort :

최선 = O(NlogN), 평균 = O(NlogN), 최악 = O(NlogN)

불안정한 정렬