2751 - Heap sort

Explain.

문제보기

Approach

Merge sort, Heap sort를 활용하여 수를 정렬.

본문에서는 Heap sort(MAX Heap)을 구현하여 Heap sort를 구현하였다.

Code

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

void swap(int arr[], int a, int b)
{
	int temp = arr[a];
	arr[a] = arr[b];
	arr[b] = temp;
}

void heapfiy(int arr[], int n, int i)
{
	int root = i;
	int left = i * 2 + 1;
	int right = i * 2 + 2;

	if (left < n && arr[root] < arr[left])
	{
		root = left;
	}

	if (right < n && arr[root] < arr[right])
	{
		root = right;
	}
	
	if (root != i)
	{
		swap(arr, root, i);
		heapfiy(arr, n, root);
	}
}

void heapsort(int arr[], int n)
{
	int i;
	for (i = n / 2; i-->0; ) 
	{
		heapfiy(arr, n, i);
	}

	for (i = n; i-->0;)
	{
		swap(arr, 0, i);
		heapfiy(arr, i, 0);
	}
}

void print(int arr[], int n)
{
	int i;

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

int main(void)
{
	int n, i;
	int *arr;
	scanf("%d", &n);

	arr = (int *)malloc(sizeof(int) * n);

	for (i = 0; i < n; ++i)
	{
		scanf("%d", &arr[i]);
	}

	heapsort(arr, n);
	print(arr, n);
}