백준알고리즘_2751_정렬 (힙정렬) (C언어)

사실 시간 복잡도 O(nlogN)의 알고리즘은 기초알고리즘 게시판에서 다 정리했지만.. 혹시 까먹었을까 싶어 한 번 풀어봤습니다. 오랜만에 짜봐서 그런지 또 시간이 꽤 걸렸네요. ㅎㅎ 시간 복잡도를 낮추려면 병합정렬, 퀵정렬, 힙정렬 세 가지 중 하나를 사용하면 됩니다. 저는 제일 좋아하는 힙정렬을 사용했습니다. 알고리즘 설명은 아래 링크글에 있습니다.

2019/12/09 - [C언어/알고리즘 및 자료구조] - 정렬알고리즘_힙 정렬 [6/8]

 

 

 

---

 

#include <stdio.h>
#include <stdlib.h>
void heap(int* arr, int n);
void swap(int* arr, int x, int y);

int main()
{
	// 배열 생성, 스택에 담기엔 너무 크다고 에러나서 동적 할당
	int* arr = (int*)malloc(sizeof(int) * 1000000);
	if (arr == NULL)
		return 1;

	// 배열 갯수 입력
	int n; 
	scanf("%d", &n); 
	// 입력 값 범위 처리 안해주면 백준 알고리즘 채점 시 런타임 에러남
	if (n < 1 || n > 1000000) 
		return 1;

	// 배열값 입력
	for (int i = 0; i < n; i++)
		scanf("%d", &arr[i]);
	
	// 힙정렬 수행
	heap(arr, n);

	// 결과 출력
	for (int i = 0; i < n; i++)
		printf("%d\n", arr[i]);
	   	 
	return 0;
}


void heap(int* arr, int n)
{
	int count = n;
	
	/* 최초 힙트리 생성 */
	int p, c;	// parent Node, Child Node	
	for (int i = 1; i < count; i++) {
		c = i;
		while (c > 0) {
			p = (c - 1) / 2;
			if (arr[p] < arr[c]) {
				swap(arr, p, c);
				c = p;
			}
			else break;
		}		
	}
	swap(arr, 0, --count);

	/* 힙정렬 수행 */
	while(count > 1) {

		p = 0;
		// 자식 노드 있는 곳까지만 보면 됨
		while (p <= (count / 2) - 1)  {
			// 첫번 째 자식 노드
			c = p * 2 + 1;	
		    // 자식 노드 중 큰 노드 선택
			if (c + 1 < count && arr[c] < arr[c + 1])
				c++;
			// 부모 노드가 자식 노드보다 작으면 교체
			if (arr[p] < arr[c]) {
				swap(arr, p, c);
				p = c;
			}
			else break;
		}
		// 마지막과 교체 후 사이즈 줄여줌
		swap(arr, 0, count-- - 1);
	}
}

/* Swap */
void swap(int* arr, int x, int y)
{
	int temp = arr[x];
	arr[x] = arr[y];
	arr[y] = temp;
}