이번에는 힙 정렬 알고리즘을 구현해 보기로 해요.
힙 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
초기 힙 구성
루트와 맨 마지막 자손 교환
n을 1 감소
반복(n: n->1)
힙 구성
루트와 맨 마지막 자손 교환
n을 1 감소
초기 힙 구성(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
반복(i:1->n)
j:=1
반복(j>0)
pa:=PARENT(j)
조건: compare(base[j], base[pa])이 0보다 크면
base[j], base[pa] 교환
j: = pa
아니면
내부 루프 탈출
힙 구성(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
반복
lc:= LCHILD(me)
rc:= RCHILD(me)
자식이 없으면
탈출
조건 왼쪽 자식만 있을 때
조건 compare(base[me],base[lc])>0일 때
base[me], base[lc] 교환
탈출
bc := 왼쪽 자식과 오른쪽 자식 중에 자료가 큰 값의 인덱스
조건 compare(base[bc],base[me])>0일 때
base[bc],base[me] 교환
아니면
탈출
//힙 정렬 #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)
{
먼저 초기 힙을 구성해야 합니다. 초기 힙은 인덱스 1에서 마지막까지 순차적으로 초기 힙을 구성합니다.
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;
}
}
}
초기 힙 구성이 끝나면 루트와 마지막 자손의 자료를 교환하고 정렬할 범위를 1줄입니다.
SWAP(base[0], base[n - 1]);//루트와 마지막 자손 교환
만약 부모의 자료보다 크지 않다면 힙을 구성한 것이므로 반복문을 탈출합니다.
ViewArr(base, n);
n--;
C 컴파일러 버전에 따라 변수 선언을 중간에 할 수 없다면 변수 선언문은 함수 시작부로 올려서 작성하세요.
size_t me;
size_t lc;
size_t rc;
이후에 힙 구성은 정렬할 범위가 1이 되기 전까지 반복합니다.
while (n>1)//반복: n이 1보다 크면
{
원래 마지막 자손이었지만 루트의 자료와 교환하여 현재 루트인 자료가 있어야 할 위치를 찾아야 합니다. 따라서 현재 자신의 인덱스를 0으로 설정하세요.
me = 0;
while (1)
{
자신의 왼쪽 자식과 오른쪽 자식의 인덱스를 구하세요.
lc = LCHILD(me);
rc = RCHILD(me);
만약 왼쪽 자식의 인덱스가 n보다 크거나 같으면 자식이 없는 것이므로 반복문을 탈출하세요.
if (lc >= n)//자식이 없음
{
break;
}
if (rc == n)//왼쪽 자식만 있음
{
만약 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;
}
}
힙 구성이 끝나면 루트와 마지막 자손의 자료를 교환한 후에 정렬 범위를 1 줄입니다.
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");
}