Page 264 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

10 int temp = a[left]; /* 루트 */
11 int child;
12 int parent;
13 for(parent = left; parent < (right + 1) / 2; parent = child) {
14 int cl = parent * 2 + 1; /* 왼쪽 자식 */
15 int cr = cl + 1; /* 오른쪽 자식 */
16 child = (cr <= right && a[cr] > a[cl]) ? cr : cl; /* 큰 값을 선택합니다. */
17 if(temp >= a[child])
18 break;
19 a[parent] = a[child];
20 }
21 a[parent] = temp;
22 }
23
24 /*--- 힙 정렬 함수 ---*/
25 void heapsort(int a[], int n)
26 {
27 int i;
28 for(i = (n - 1) / 2; i >= 0; i--)
1
29 downheap(a, i, n - 1);
30 for(i = n - 1; i > 0; i--) {
31 swap(int, a[0], a[i]);
2
32 downheap(a, 0, i - 1);
33 }
34 }
실행 결과
35
36 int main(void) 힙 정렬
요소 개수 : 7
37 {
x[0] : 22
38 int i, nx;
x[1] : 5
39 int *x; /* 배열의 첫 번째 요소에 대한 포인터 */ x[2] : 11
40 puts("힙 정렬"); x[3] : 32
41 printf("요소 개수 : "); x[4] : 120
42 scanf("%d", &nx); x[5] : 68
x[6] : 70
43 x = calloc(nx, sizeof(int));
오름차순으로 정렬했습니다.
44 for(i = 0; i < nx; i++) {
x[0] = 5
45 printf("x[%d] : ", i); x[1] = 11
46 scanf("%d", &x[i]); x[2] = 22
47 } x[3] = 32
48 heapsort(x, nx); /* 배열 x를 힙 정렬 */ x[4] = 68
x[5] = 70
49 puts("오름차순으로 정렬했습니다.");
x[6] = 120
50 for(i = 0; i < nx; i++)

264 C 알고리즘