[알고리즘] 정렬 알고리즘 - 힙 정렬 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

 

- 힙 정렬 :

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)

불안정한 정렬