# Heap_Sort

Nov 17th, 2020
490
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. //Sắp xếp tăng dần sử dụng Heap_Sort
2.
3. #include <stdio.h>
4.
5. void Out_Put(int n, int A[]);
6. void In_Put(int n, int A[]);
7. void Heap_Sort(int A[], int length,bool (*comparisonFunc)(int,int));
8. void Build_Max_Heap(int A[], int length, bool(*comparisonFunc)(int,int));
9. void swap(int& x, int& y);
10. void Max_Heap(int A[], int i, int Heap_Size, bool (*comparisonFunc)(int, int));
11. bool ascending(int left, int right);
12. bool descending(int left, int right);
13.
14. int main()
15. {
16.     int n;
17.     printf("Nhap so luong phan tu cua mang !\n");
18.     scanf_s("%d", &n);
19.     int* A = new int[n];
20.     In_Put(n, A);
21.
22.     //Sắp xếp tăng dần
23.     printf("Sap xep tang dan : ");
24.     Heap_Sort(A, n,ascending);
25.     Out_Put(n, A);
26.
27.     //Sắp xếp giảm dần
28.     printf("\nSap xep giam dan : ");
29.     Heap_Sort(A, n, descending);
30.     Out_Put(n, A);
31.
32.     delete[] A;
33.     return 0;
34. }
35.
36. void Heap_Sort(int A[], int length, bool (*comparisonFunc)(int, int))
37. {
38.     int Heap_Size = length;
39.     Build_Max_Heap(A, length,comparisonFunc);
40.
41.     for (int i = length - 1; i >= 1; i--)
42.     {
43.         swap(A[0], A[i]);
44.         Heap_Size = Heap_Size - 1;
45.         Max_Heap(A, 0, Heap_Size,comparisonFunc);
46.     }
47. }
48.
49. void Build_Max_Heap(int A[], int length, bool (*comparisonFunc)(int,int))
50. {
51.     int Heap_Size = length;
52.     for (int i = length / 2 - 1; i >= 0; i--)
53.     {
54.         Max_Heap(A, i, length,comparisonFunc);
55.     }
56. }
57.
58. //Hàm đổi chỗ 2 số
59. void swap(int &x, int &y)
60. {
61.     int tmp = x;
62.     x = y;
63.     y = tmp;
64. }
65.
66. //Sắp xếp tăng dần
67. bool ascending (int left, int right)
68. {
69.     return left > right;
70. }
71.
72. //Sắp giảm dần
73. bool descending(int left, int right)
74. {
75.     return left < right;
76. }
77.
78. void Max_Heap(int A[], int i, int Heap_Size, bool (*comparisonFunc)(int , int))
79. {
80.     int l = 2 * i + 1;
81.     int r = 2 * i + 2;
82.     int largest;
83.     if ((l < Heap_Size) && comparisonFunc(A[l],A[i]))
84.     {
85.         largest = l;
86.     }
87.     else
88.     {
89.         largest = i;
90.     }
91.     if (r<Heap_Size && comparisonFunc(A[r],A[largest]))
92.     {
93.         largest = r;
94.     }
95.     if (largest != i)
96.     {
97.         swap(A[i],A[largest]);
98.         Max_Heap(A, largest, Heap_Size,comparisonFunc);
99.     }
100.
101. }
102.
103. //Xuất mảng
104. void Out_Put(int n, int A[])
105. {
106.     for (int i = 0; i < n; i++)
107.     {
108.         printf("%d ", A[i]);
109.     }
110. }
111.
112. //Nhập mảng
113. void In_Put(int n, int A[])
114. {
115.     for (int i = 0; i < n; i++)
116.     {
117.         scanf_s("%d", &A[i]);
118.     }
119. }
RAW Paste Data