AnhVan1712

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

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×