[C/C++] 힙 정렬(heap sort)로 오름차순 정렬하기

힙 정렬이란?

힙 정렬은 힙을 사용하여 정렬하는 알고리즘입니다. 그러면 힙 이란 무엇인가? 

힙은 부모의 값이 자식의 값보다 항상 크다는 조건을 만족하는 완전이진트리입니다.

 

예를 들어 다음과 같이 1부터 10까지의 수를 무작위로 섞어놓은 배열이 있습니다.

값	5	6	10	4	3	8	7	1	2	9
위치	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]

 

먼저 힙 상태를 만들어야 합니다. 이 과정을 heapify라고 합니다.

자기와 자기 자식의 요소들을 비교하여 자기보다 큰 값을 가지는 자식 노드가 있다면 자리를 바꾼다. 여기서 교환이 일어나면 당연히 위에 노드도 점검을 해야 합니다.

 

힙 정렬 알고리즘은 다음과 같습니다.

힙 상태인 데이터에서 루트와 최하단 노드를 교체합니다.(그러면 최하단 노드는 정렬이 완료됩니다.)

힙 상태로 만들어 줍니다.

(* 루트 : 최상단 노드)

 

위 두 과정을 반복하는 것이 힙 정렬입니다.

#include <stdio.h>

//heapify, 힙 상태 만들기 
void heapify(int *arr, int size){
	for(int i=1;i<size;++i){
		int child = i;
		do{
			//자식 노드가 부모 노드보다 크면 교환
			int root = (child-1)/2;
			if(arr[root]<arr[child]){
				int temp = arr[root];
				arr[root] = arr[child];
				arr[child] = temp;
			}
			child = root;
		}while(child!=0);	//최상단 노드까지 점검
	}
}

//최상단 노드와 최하단 노드 교체
void heap(int *arr, int *size){
	int temp = arr[0];
	arr[0] = arr[*size-1];
	arr[*size-1] = temp;
	--(*size);
}

int main(){
	
	int size = 10;
	//무작위 배열
	int arr[10] = {5, 6, 10, 4, 3, 8, 7, 1, 2, 9};
	
	//힙정렬
	for(int i=0;i<10;++i){
		heapify(arr, size);
		heap(arr, &size);
	}
	
	//출력 
	for(int i=0;i<10;++i){
		printf("%d ", arr[i]);
	}
	
	return 0;
}

 

결과값:

1 2 3 4 5 6 7 8 9 10

 

힙 정렬은 병합 정렬과 달리 임시 저장을 위한 메모리 사용이 필요 없어서 병합 정렬의 단점을 보완한 정렬방법입니다. 또한, 병합 정렬과 마찬가지로 항상 시간 복잡도를 N*log(N)을 보장할 수 있습니다.

 

 

힙 정렬의 시간 복잡도(or 빅오)는 O(N*log(N))입니다.