힙 정렬 (Heap-Sort)

힙 정렬 (Heap-Sort)

- 힙 정렬의 수행시간은 O(n log n) 이다.

- 삽입 정렬과 같이 내부 정렬이다.( 정렬시 입력 배열의 원소를 초과해 배열 밖에 저장하는 일이 없다)

동작 원리

1. 최대(최소) 힙을 구성한다 

2. 루트에 위치한 수와 가장 작은 수를 교환

3. 교환한 수를 제외하고 힙 특성을 유지

4. 2-3의 과정 반복

소스

1. #include<stdio.h>
2.  
3. int * maxheapify(int *,int); // max heap 유지함수
4.  
5. int * buildmaxheap(int *, int); // heap 만들기 함수
6.  
7. int * heapsort(int *, int); // heap 정렬함수
8.  
9. int heapsize;
10.  
11. int main(void)
12. {
13.     int arr[10] = {69, 10, 30, 2, 16, 8, 31, 30, 35, 70 }; // 초기 입력 값
14.     int * heap;
15.     int a = 0;
16.  
17.     printf("변경전 : ");
18.     for(a= 0;a<10;a++)
19.     {
20.         printf("%d ",arr[a]);
21.     }
22.  
23.     heapsize = sizeof(arr)/sizeof(arr[0]);
24.  
25.     heap = heapsort(arr, heapsize);
26.    
27.    
28.  
29.     printf("\n변경후 : ");
30.     for(a= 0;a<10;a++)
31.     {
32.         printf("%d ",arr[a]);
33.     }
34.  
35.  
36.     return 0;
37. }
38.  
39. int * heapsort(int *arr, int size)
40. {
41.     int ch = 0;
42.     int a = 9;
43.     int temp = 0;
44.     int build = 3;
45.     arr = buildmaxheap(arr,size);
46.  
47.     for(;a > 1; a --) // 루트와 맨끝 노드의 값을 변경
48.     {
49.         temp = (*arr);
50.         (*arr) = (*(arr+a));
51.         (*(arr+a)) = temp;
52.  
53.         heapsize --;
54.  
55.         arr=    maxheapify(arr,0);
56.     }
57.    
58.     return arr;
59. }  
60.  
61. int * buildmaxheap(int * arr, int a)
62. {
63.     int b = a/2 -1;
64.  
65.     for(;b >= 0 ;b--)
66.     {
67.         maxheapify(arr,b);
68.     }
69.  
70.     return arr;
71. }
72.  
73. int * maxheapify(int  *arr, int a)
74. {
75.     int left = 0;
76.     int right = 0;
77.     int largest = 0;
78.     int temp =  0;
79.     int ch = 0;
80.  
81.     if(a == 0)
82.     {
83.         left = 1;
84.         right = 2;
85.     }
86.     else
87.     {
88.         left = a*2+1;
89.         right = a*2+2;
90.     }  
91.  
92.     if(left < heapsize && (*(arr+left)) >= (*(arr+a))) // 왼쪽 노드가 더 클때
93.         largest = left;
94.     else
95.         largest = a;    // 아니면 루트
96.  
97.     if(right < heapsize && (*(arr+right)) >= (*(arr+largest))) // 오른쪽 노드가 클때
98.         largest = right;
99.  
100.     if(largest != a) //더 큰값으로 루트를 교환한다.
101.     {
102.         temp = (*(arr+a));
103.         (*(arr+a)) = (*(arr+largest));
104.         (*(arr+largest)) = temp;
105.  
106.         maxheapify(arr,largest);
107.     }
108.  
109.     return arr;
110. }

결과