[C언어] 히프 정렬 알고리즘 (프로그램 소스)

소개글

C언어 중, Heap Sort 프로그램입니다.
가장 기본적인 코드로 구현하였으며, 실행화면도 캡쳐하여 넣었습니다.

목차

없음

본문내용

#include <stdio.h>
#define swap(x, y, t) ((t)=(x), (x)=(y), (y)=(t))

int L[15] = { 10, 4, 7, 1, -2, 12, 28, 66, 9, 3, 5, 7, 6, 21, 11 };

void print_data(int L[], int n)
{
int i;

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

void Max_heap(int L[], int root, int n)
{
int child, root_data;

root_data = L[root];
child = root * 2 + 1;

// 자식 노드가 있는 한 반복
while (child < n)
{
// 자식 노드 중 큰 것을 선택
if ((child < n) && (L[child] < L[child+1]))
child = child + 1;

if (root_data > L[child])
break;

else
{
L[(child-1) / 2] = L[child]; // 위로 이동
child = child * 2 + 1 ;
}
}

L[(child-1) / 2] = root_data;
}

void Heap_Sorting(int L[], int n)
{
int i, temp;

// 최대 히프 구조 생성
for (i = (n-1)/2; i >= 0; i--)
Max_heap(L, i, n-1);

// 실제 정렬
for (i = n-2; i >= 0; i--)
{
// 두 원소 L[0], L[i+1] 교환
swap(L[0], L[i+1], temp);
Max_heap(L, 0, i);

참고 자료

없음