SHARE
TWEET

финальная задача

a guest Sep 17th, 2019 86 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <random>
  5. #include <ctime>
  6. #include <time.h>
  7.  
  8. using namespace std;
  9.  
  10. vector<int> randomVector(size_t size)
  11. {
  12.     vector<int> v(size);
  13.     random_device r;
  14.     generate(v.begin(), v.end(), [&] {return r(); });
  15.     return v;
  16. }
  17.  
  18. bool compare_as_ints(double i, double j)
  19. {
  20.     return (int(i) < int(j));
  21. }
  22.  
  23. void heapify(vector<pair<int, int>>& a, int i, int n)
  24. {
  25.     int l = 2 * i;
  26.     int r = 2 * i + 1;
  27.  
  28.     int large;
  29.     if (l <= n && a[l] > a[i])
  30.         large = l;
  31.     else
  32.         large = i;
  33.  
  34.     if (r <= n && a[r] > a[large])
  35.         large = r;
  36.  
  37.     if (large != i)
  38.     {
  39.         swap(a[i], a[large]);
  40.         heapify(a, large, n);
  41.     }
  42. }
  43. void build(vector<pair<int, int>>& a, int n)
  44. {
  45.     for (int k = a.size() / 2; k >= 1; k--)
  46.     {
  47.         heapify(a, k, n);
  48.     }
  49. }
  50. vector<int> heapsort(vector<int>& a)
  51. {
  52.     int n = a.size();
  53.     vector<pair<int, int>> t(n + 1);
  54.     for (int i = 1; i <= n; i++)
  55.     {
  56.         t[i] = { a[i - 1], i };
  57.     }
  58.     build(t, n);
  59.  
  60.     for (int i = n; i >= 2; i--)
  61.     {
  62.         swap(t[i], t[1]);
  63.         heapify(t, 1, i - 1);
  64.     }
  65.  
  66.     vector<int> res(n);
  67.     for (int i = 1; i <= n; i++)
  68.     {
  69.         res[i - 1] = t[i].first;
  70.     }
  71.     return res;
  72. }
  73.  
  74. int main()
  75. {
  76.     int n;
  77.     cin >> n;
  78.  
  79.     vector<int> a(randomVector(n)), c(n);
  80.     for (int i = 0; i < n; i++)
  81.     {
  82.         c[i] = a[i];
  83.     }
  84.  
  85.     clock_t time;
  86.     time = clock();
  87.     auto b = heapsort(a);   //pyramide stable sort 
  88.     time = clock() - time;
  89.  
  90.  
  91.     clock_t time1;
  92.     time1 = clock();
  93.     stable_sort(c.begin(), c.end());    //stable_sort
  94.     time1 = clock() - time1;
  95.  
  96.     cout << "time of pyramide stable sort: " << (double)time / CLOCKS_PER_SEC << endl;
  97.     cout << "time of stable_sort: " << (double)time1 / CLOCKS_PER_SEC << endl;
  98. }
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