Advertisement
Guest User

Untitled

a guest
Apr 10th, 2020
184
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.48 KB | None | 0 0
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <algorithm>
  4. #include <random>
  5. #include <ctime>
  6. using namespace std;
  7. #include <algorithm>
  8. #include <iomanip>
  9. #include <iostream>
  10. #include <nmmintrin.h>
  11. #include <vector>
  12.  
  13. using namespace std;
  14.  
  15. void FillInc(int n, int* a);
  16. void FillDec(int n, int* a);
  17. void FillRand(int n, int* a);
  18. void swap(int* xp, int* yp);
  19. void PrintMas(int n, int* a);
  20. void heapify(int* a, int l, int r, int& c, int& m);
  21. int HeapSort(int n, int* a);
  22. void PrintTabl();
  23.  
  24. int main() {
  25.     srand(time(nullptr));
  26.     int n;
  27.     int* a;
  28.     cin >> n;
  29.     a = new int[n+1];
  30.     FillRand(n, a);
  31.     PrintMas(n, a);
  32.     cout << endl;
  33.     HeapSort(n, a);
  34.     PrintMas(n, a);
  35.     PrintTabl();
  36. }
  37.  
  38. void heapify(int* a, int l, int r, int& c, int& m) {
  39.     int x = a[l], j;
  40.     int i = l;
  41.     ++m;
  42.     while (i <= r / 2) {
  43.         j = 2 * i;
  44.         ++c;
  45.         if ((j < r) && (a[j + 1] <= a[j]))
  46.             j++;
  47.         ++c;
  48.         if (x <= a[j]) {
  49.             break;
  50.         }
  51.         ++m;
  52.         a[i] = a[j];
  53.         i = j;
  54.     }
  55.     ++m;
  56.     a[i] = x;
  57. }
  58.  
  59. int HeapSort(int n, int* a) {
  60.     int l = n / 2, c = 0, m = 0;
  61.     while (l > 0) {
  62.         heapify(a, l, n, c, m);
  63.         --l;
  64.     }
  65.     int r = n;
  66.     while (r > 1) {
  67.         m += 3;
  68.         swap(a[1], a[r]);
  69.         r--;
  70.         heapify(a, 1, r, c, m);
  71.     }
  72.     int T = c + m;
  73.     return T;
  74. }
  75.  
  76. void FillInc(int n, int* a) {
  77.     for (int i = 1; i <= n; ++i) {
  78.         a[i] = i;
  79.     }
  80. }
  81.  
  82. void FillDec(int n, int* a) {
  83.     for (int i = n; i >= 1; i--) {
  84.         a[n - i] = i;
  85.     }
  86. }
  87. void FillRand(int n, int* a) {
  88.     for (int i = 1; i <= n; ++i) {
  89.         a[i] = rand() % n;
  90.     }
  91. }
  92. void swap(int* xp, int* yp) {
  93.     int temp = *xp;
  94.     *xp = *yp;
  95.     *yp = temp;
  96. }
  97. void PrintMas(int n, int* a) {
  98.     for (int i = 1; i <= n; ++i) {
  99.         cout << a[i] << " ";
  100.     }
  101. }
  102.  
  103. void PrintTabl() {
  104.     int n = 1, FR = 0, FD = 0, FI = 0;
  105.     int* a = new int[n+1];
  106.     cout << endl << "|                 HeapSort               |" << endl;
  107.     cout << "| n |  FillInc  |  FillDec  |  FillRand  |" << endl;
  108.  
  109.     for (int n = 100; n <= 500; n += 100)
  110.     {
  111.         FillRand(n, a);
  112.         FR = HeapSort(n, a);
  113.         FillInc(n, a);
  114.         FI = HeapSort(n, a);
  115.         FillDec(n, a);
  116.         FD = HeapSort(n, a);
  117.         cout << "|" << n << "|" << setw(11) << FI << "|" << setw(11) << FD << "|"
  118.             << setw(12) << FR << "|" << endl;
  119.     }
  120.  
  121.     delete[] a }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement