2-1) [C] 힙 정렬(Heap Sort)

1) 힙 정렬이란?

힙이라는 데이터 구조를 사용하여 정렬하는데, 최소값이나 최대값을 찾는데 최적화되어있는 완전이진트리 형태의 자료구조이다.

2) 힙 정렬의 시간복잡도

힙 정렬을 위해 n개의 숫자를 힙에 저장할 때 걸리는 시간은 O(n log n)이 된다. 1회 추가에 O(log n)의 시간이 걸리기 때문이다.

또한, 각 라운드에서 최대 숫자를 꺼내서 힙을 재구축하는 데 걸리는 시간은 O(log n)이다. 라운드 수는 n이므로 힙이 완성된 후에 정렬하는 시간도 n*O(log n)이 된다. 따라서 힙 정렬의 계산시간은 전체적으로  O(n log n)이다. 버블 정렬, 선택 정렬, 삽입 정렬의 O(n^2)에 비해 빠른 속도지만, 복잡한 데이터 구조를 구현하는 것이 어렵다.

point! 힙 정렬의 전체 시간 복잡도는 힙 생성(Heapify)알고리즘 시간 복잡도 O(log N) * 전체 데이터 수 N = O(N * logN)

 

3) 힙 정렬 구현

1. 배열을 최대 힙 구조로 변환

2. 큰 수 부터 하나씩 추출

#include <stdio.h>

int size = 8;
int heap[8] = { 6, 5, 8, 4, 1, 7, 2, 3 };

int main() {
	// 트리 구조를 최대 힙 구조로 변환
	for (int i = 1; i < size; i++) {
		int child = i;
		do {
			int root = (child - 1) / 2;
			if (heap[root] < heap[child]) {
				int temp = heap[root];
				heap[root] = heap[child];
				heap[child] = temp;
			}
			child = root;
		} while (child != 0);
	}
	// 힙 크기를 줄이면서 반복적으로 힙을 구성
	for (int i = size - 1; i >= 0; i--) {
		int temp = heap[0];
		heap[0] = heap[i];
		heap[i] = temp;
		int root = 0;
		int child = 1;
		do {
			child = 2 * root + 1;
			// 자식 중 더 큰 값을 찾기
			if (heap[child] < heap[child + 1] && child < i - 1) {
				child++;
			}
			// root보다 자식이 더 크면 교환
			if (heap[root] < heap[child] && child < i) {
				int temp = heap[root];
				heap[root] = heap[child];
				heap[child] = temp;
			}
			root = child;
		} while (child < i);
	}
	for (int i = 0; i < size; i++)
		printf("%d ", heap[i]);

	return 0;
}

결과화면

1 2 3 4 5 6 7 8