[C언어 알고리즘] 3.5.4 힙 정렬 알고리즘 소스 코드
//힙 정렬
#include <stdio.h>
#define SWAP(a,b) {int t; t = a; a=b; b=t;}//a와 b를 교환
#define LCHILD(me) (2*me +1)
#define RCHILD(me) (LCHILD(me)+1)
#define PARENT(me) ((me-1)/2)
void ViewArr(int *arr, int n);
void HeapSort(int *base, size_t n);
int main(void)
{
int arr[10] = { 9,4,3,10,5,8,7,6,2,1 };
ViewArr(arr, 10);
HeapSort(arr, 10);
ViewArr(arr, 10);
return 0;
}
void HeapSort(int *base, size_t n)
{
for (size_t i = 1; i<n; i++)
{
int j = i;
while (j>0)//루트가 아니면 반복
{
int pa = PARENT(j);//부모 인덱스를 구하기
if (base[j]< base[pa]) //부모보다 크면
{
SWAP(base[j], base[pa]);//부모와 교환
ViewArr(base, n);
j = pa;
}
else
{
break;
}
}
}
SWAP(base[0], base[n - 1]);//루트와 마지막 자손 교환
ViewArr(base, n);
n--;
size_t me;
size_t lc;
size_t rc;
while (n>1)//반복: n이 1보다 크면
{
me = 0;
while (1)
{
lc = LCHILD(me);
rc = RCHILD(me);
if (lc >= n)//자식이 없음
{
break;
}
if (rc == n)//왼쪽 자식만 있음
{
if (base[me]< base[lc])
{
SWAP(base[me], base[lc]);
ViewArr(base, n);
}
break;
}
int bc = lc;
if (base[lc]< base[rc])
{
bc = rc;
}
if (base[bc]> base[me])
{
SWAP(base[bc], base[me]);
ViewArr(base, n);
me = bc;
}
else
{
break;
}
}
SWAP(base[0], base[n - 1]);//루트와 마지막 자손 교환
ViewArr(base, n);
n--;
}
}
void ViewArr(int *arr, int n)
{
int i = 0;
for (i = 0; i<n; i++)
{
printf("%2d ", arr[i]);
}
printf("\n");
}
'언어 자료구조 알고리즘 > 디딤돌 알고리즘 (C언어)' 카테고리의 다른 글
| [C언어 알고리즘] 4.2.1 이진 탐색 알고리즘 소스 코드 (0) | 2016.12.01 |
|---|---|
| [C언어 알고리즘] 4.2 이진 탐색 알고리즘 (0) | 2016.12.01 |
| [C언어 알고리즘] 4.1.1 최소값(최대값) 찾기 알고리즘 소스 코드 (0) | 2016.12.01 |
| [C언어 알고리즘] 4.1 최소값(최대값) 찾기 알고리즘 (0) | 2016.12.01 |
| [C언어 알고리즘] 4. 분할정복 알고리즘 (0) | 2016.12.01 |
| [C언어 알고리즘] 3.5.3 힙 정렬 알고리즘 구현 (0) | 2016.11.30 |
| [C언어 알고리즘] 3.5.2 힙 정렬 알고리즘 성능 분석 (0) | 2016.11.30 |
| [C언어 알고리즘] 3.5.1 힙 정렬 알고리즘 소개 (0) | 2016.11.30 |
| [C언어 알고리즘] 3.5 힙 정렬(Heap Sort) 알고리즘 (0) | 2016.11.30 |
| [C언어 알고리즘] 3.4.4 이진 탐색 트리 소스 코드 (1) | 2016.11.30 |