[대학교 알고리즘] HeapSort

void MakeHeap(int A[ ], int Root, int LastNode) {
/* 입력 : A[Root:LastNode] - 히프로 변환할 배열. 입력 당시에
  A[Root+1:LastNode] 는 이미 히프 구조이다.
출력 : A[Root:LastNode] - 최대값 히프 */
int Parent, LeftSon, RightSon, Son, RootValue;
Parent = Root;
RootValue = A[Root];
LeftSon = 2 * Parent + 1;
RightSon = LeftSon + 1;
while (LeftSon <= LastNode) {
if (RightSon <= LastNode && A[LeftSon] < A[RightSon])
Son = RightSon;
else Son = LeftSon;
if (RootValue < A[Son]) {
A[Parent] = A[Son];
Parent = Son;
LeftSon = Parent * 2 + 1;
RightSon = LeftSon + 1;
}
else break;
}
A[Parent] = RootValue;
}

void HeapSort(int A[ ], int n) {
/* 입력: A[0:n-1] - 정렬할 배열, n - 정렬할 원소의 개수.
출력: A[0:n-1] - 정렬된 배열. */
int i;
for (i=n/2; i>0; i--)
MakeHeap(A, i-1, n-1);
for (i=n-1; i>0; i--) {
Swap(&A[0], &A[i]);
MakeHeap(A, 0, i-1);
}
}