Ledger Nano X - The secure hardware wallet
SHARE
TWEET

Untitled

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