[정렬] 힙 정렬

 

1. 자료구조
   1. 연결 리스트
   2. 이진 트리
   3. 스택
   4. 큐
   5. 해시
2. 정렬
   1. 버블 정렬
   2. 선택 정렬
   3. 삽입 정렬
   4. 퀵 정렬
   5. 힙 정렬
3. 알고리즘
   1. 재귀 함수
   2. 너비 우선탐색(BFS)
   3. 깊이 우선탐색(DFS)
   4. 다익스트라

---

 

힙 정렬(Heap Sort)

완전 이진트리

힙 정렬은 완전 이진 트리의 조건을 만족해야한다.

완전 이진 트리란 마지막 LEVEL를 제외한 나머지 LEVEL의 노드가 모두 NULL이 아니여야하고

마지막 LEVEL은 왼쪽부터 채워져 있는 이진트리를 말한다.

 

---

 

Heapify(최대힙 구성)

Heapify()

각 노드의 값이 자식노드(왼쪽, 오른쪽)보다 항상 큰값을 가진 이진트리를 만든다.

1번 노드부터 부모 노드와 비교하며 크면 교환해준다.(0번 노드까지)

 

 

Heap Sort

Heap_Sort()

1. 마지막 노드와 0번째 노드를 교환하다.
2. 마지막 노드를 제외한 나머지 노드로 최대힙을 구한다.
3. 1~2번을 반복한다.

 

---

 

소스코드

#define __main

#ifdef __main

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_SIZE 10

void Init(int arr[]) {
	srand(time(NULL));
	for (int i = 0; i < MAX_SIZE; i++) {
		// 임의의 정수 입력
		arr[i] = rand() % 10000;
	}
}

void swap(int* a, int* b) {
	int tmp;

	tmp = *a;
	*a = *b;
	*b = tmp;
}

void Heapify(int arr[], int n) {
	for (int i = 1; i < n; i++) {
		int c = i;
		do {
			int root = (c - 1) / 2;
			if (arr[root] < arr[c]) swap(&arr[root], &arr[c]);
			c = root;
		} while (c != 0);
	}
}

void Heap_Sort(int arr[]) {
	Heapify(arr, MAX_SIZE);
	
	for (int i = MAX_SIZE - 1; i >= 0; i--) {
		if (arr[0] > arr[i]) {
			swap(&arr[0], &arr[i]);
			Heapify(arr, i - 1);
		}
	}
}

void Print(int arr[]) {
	for (int i = 0; i < MAX_SIZE; i++) {
		printf("[%d] -> %d\n", i, arr[i]);
	}
	printf("\n--------------------\n\n");
}

int main() {
	int arr[MAX_SIZE];

	Init(arr);

	Print(arr);

	Heap_Sort(arr);

	Print(arr);

	return 0;
}

#endif