AnhVan1712

Heap_Sort

Nov 17th, 2020
449
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