[알고리즘, C] 힙 정렬(Heap Sort) 구현

<힙 정렬 구현>

https://sevenshards.tistory.com/9

[자료구조, C] 배열 기반의 힙(Heap) 구현

이전에 작성했던 힙을 이용하여 정렬을 수행.

그래서 기존에 작성했던 Heap.h, Heap.c를 이용하였다.

 

[HeapSort.c]

/*
* 알고리즘 - 힙 정렬(Heap Sort)
* 파일명: HeapSort.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-26
* 이전 버전 작성 일자:
* 버전 내용: 간단한 힙 정렬 구현
* 이전 버전 내용:
*/

#include <stdio.h>
#include "Heap.h"

// 힙에 부여할 정렬의 기준
// 첫 번째 인자의 우선 순위가 크다면, 0보다 큰 값을 반환 (오름차순)
// 두 번째 인자의 우선 순위가 크다면, 0보다 작은 값을 반환 (내림차순)
// 첫 번째 인자와 두 번째 인자의 우선 순위가 같다면 0을 반환
int PriComp(int n1, int n2)
{
	return n2 - n1; // 오름차순
	//return n1 - n2; // 내림차순
}

void HeapSort(int arr[], int n, PriorityComp pc)
{
	Heap heap;
	int i;

	// 힙 초기화 - 힙 구조체와 데이터의 우선순위를 판별할 함수를 인자로 전달
	HeapInit(&heap, pc);

	// 정렬 대상을 가지고 힙을 구성
	for (i = 0; i < n; i++)
		HInsert(&heap, arr[i]); // 힙 정렬 단계1) 데이터를 모두 힙에 넣는다.

	// 힙에 들어간 값을 다시 꺼내서 정렬
	for (i = 0; i < n; i++)
		arr[i] = HDelete(&heap); // 힙 정렬 단계2) 데이터를 모두 꺼낸다.
}

int main()
{
	int arr[4] = { 3, 4, 2, 1 };
	int i;

	HeapSort(arr, sizeof(arr) / sizeof(int), PriComp);

	for (i = 0; i < 4; i++)
		printf("%d ", arr[i]);

	printf("\n");
	
	return 0;
}

[지금부터는 약간(?) 복잡하지만 유용한 정렬 알고리즘]

지금까지 다뤘던 버블, 선택, 삽입 정렬의 경우에는 모두 $O(n^2)$의 시간복잡도를 지닌 알고리즘이었다.

데이터 수가 적을 때에는 사용할만한 알고리즘이라고 볼 수 있다.

하지만 실제로 데이터의 수가 100만개, 1000만개라고 한다면?

사용하기에는 적합한 알고리즘은 아니라는 것이다.

시간 복잡도가 안좋지만, 구현하기에는 아주 쉽다는 장점이 있다는 것.

힙 정렬부터 이후에 다루게 되는 정렬 알고리즘은 지금까지 구현했던 것보다는 약간(?) 복잡하다.

그래서 구현하는 데에 있어서는 이전에 다뤘던 정렬 알고리즘들에 비해서는 상대적으로 어렵다.

하지지만 성능 면에 있어서는 $O(n^2)$ 의 시간 복잡도를 갖지 않는 유용한 알고리즘들이다.

 

[힙 정렬의 이해]

기존에 구현했던 힙을 활용해서 힙에 입력하고 출력만 하면 되는 프로그램.
힙의 기본 구조를 다시 한 번 복습하는 차원에서 정리하자면 다음과 같은 특성을 가진다.

“값이 가장 큰(또는 작은) 노드가 루트 노드이며, 모든 노드는 자식 노드보다 값이 커야(또는 작아야) 한다”

이걸 우선순위로 바꿔서 표현하면 다음과 같은 특성을 가지게 된다.

“루트 노드는 우선 순위가 가장 높은 노드이고, 모든 노드는 자식 노드보다 우선 순위가 높아야 한다.”
그렇기 때문에 힙에 들어가는 데이터는 입력을 받음과 동시에 정렬이 된다.
그리고 저장된 데이터를 출력하면 프로그래머가 정한 우선순위에 따라 정렬되어 출력된다.
힙은 이처럼 저장 목적 외에도 정렬의 도구로 사용이 가능하다.

[성능 평가]

이전에 힙에서의 데이터 저장과 삭제에 대한 시간 복잡도를 다뤘었다.
힙에 데이터가 저장되고 삭제되는 데에는 $O(log_2n)$ 만큼의 시간이 걸린다.
그 이유는 복습 차원에서 다시 정리한다면, 완전 이진 트리의 특성과 관련이 있다.

완전 이진 트리의 높이가 하나 증가할 때마다 데이터의 총 갯수는 2배씩 증가한다.
비교 연산은 높이가 하나 증가할 때마다 1회 증가하므로 $log_2n$ 만큼 증가하게 되는 것이다.
삽입과 삭제를 하나로 묶는다 하면 실제로는 $O(2log_2n)$ 만큼의 시간이 걸린다.
하지만 빅-오 표기법에서는 최고 차항만 따지면 되므로 $O(log_2n)$의 시간이 걸린다고 볼 수 있다.
정렬 과정에서 대한 시간 복잡도 계산은 전체 데이터의 양이 $n$이라고 했을 때, 데이터의 양만큼 걸린 시간이다.
그렇기 때문에 힙 정렬의 시간 복잡도는 $O(nlog_2n)$이 된다.