Advertisement
Korotkodul

QuickSort_v7

Sep 30th, 2023 (edited)
817
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.97 KB | None | 0 0
  1. #include <cmath>
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. using std::cin;
  6. using std::cout;
  7. using std::max;
  8. using std::min;
  9. using std::string;
  10. using std::vector;
  11.  
  12. bool sh = 0;
  13.  
  14. void swap(int* p1, int* p2) {
  15.   int t = *p1;
  16.   *p1 = *p2;
  17.   *p2 = t;
  18. }
  19.  
  20.  
  21. vector<int> Partition(vector<int> aa, int xx) {
  22.   //делим на < и >=
  23.   int nn = aa.size();
  24.   int ll = -1;
  25.   for (int ii = 0; ii < nn; ++ii) {
  26.     if (aa[ii] < xx) {
  27.       int* p1 = &aa[ii];
  28.       int* p2 = &aa[ll + 1];
  29.       swap(p1, p2);
  30.       ll++;
  31.     }
  32.   }
  33.   //делим на = и >
  34.   for (int ii = ll + 1; ii < nn; ++ii) {
  35.     if (aa[ii] == xx) {
  36.       int* p1 = &aa[ii];
  37.       int* p2 = &aa[ll + 1];
  38.       swap(p1, p2);
  39.       ll++;
  40.     }
  41.   }
  42.   return aa;
  43. }
  44.  
  45. int get_med(vector<int> vv) {
  46.   for (int ii = 0; ii < 5; ++ii) {
  47.     for (int jj = 0; jj < 4; ++jj) {
  48.       if (vv[jj] > vv[jj + 1]) {
  49.         int* p1 = &vv[jj];
  50.         int* p2 = &vv[jj + 1];
  51.         swap(p1, p2);
  52.       }
  53.     }
  54.   }
  55.   /*if (sh) {
  56.     cout << "vv sorted\n";
  57.     for (int ii: vv) {
  58.       cout << ii << ' ';
  59.     }
  60.     cout << "\n\n";
  61.   }*/
  62.   return vv[2];
  63. }
  64.  
  65. int inf = 2e9;
  66.  
  67. vector<int> DQS(vector<int> aa);
  68.  
  69. int QuickSelect(vector<int> med) {
  70.   while (med.size() % 5 != 0) {
  71.     med.push_back(inf);
  72.   }
  73.   if (sh) {
  74.     cout << "QuickSelect\n";
  75.     cout << "med\n";
  76.     for (int ii: med) {
  77.       cout << ii << ' ';
  78.     }
  79.     cout << "\n";
  80.   }
  81.  
  82.   vector<int> new_med;
  83.   for (int ii = 0; ii < med.size(); ii += 5) {
  84.     vector<int> vv = {med[ii], med[ii + 1], med[ii + 2], med[ii + 3], med[ii + 4]};
  85.     int kk = get_med(vv);
  86.     new_med.push_back(kk);
  87.   }
  88.   if (new_med.size() == 1) {
  89.     return new_med[0];
  90.   } else if (new_med.size() == 2) {
  91.     if (new_med[0] != inf) {
  92.       return new_med[0];
  93.     }
  94.     return new_med[1];
  95.   } else if (new_med.size() <= 5) {
  96.       for (int ii: new_med) {
  97.         if (ii != inf) {
  98.           return ii;
  99.         }
  100.       }
  101.       return new_med[2];
  102.   }
  103.   if (sh) {
  104.     cout << "new_med\n";
  105.     for (int ii: new_med) {
  106.       cout << ii << ' ';
  107.     }
  108.     cout << "\n\n";
  109.   }
  110.   new_med = DQS(new_med);
  111.   int res = QuickSelect(new_med);
  112.   if (sh) {
  113.     cout << "QuickSelect res = " << res << "\n\n";
  114.   }
  115.   return res;
  116. }
  117.  
  118. vector<int> DQS(vector <int> aa) {
  119.     if (aa.size() == 1) {
  120.       return aa;
  121.     }
  122.     if (aa.size() == 2) {
  123.       return {min(aa[0], aa[1]), max(aa[0], aa[1])};
  124.     }
  125.     if (sh) {
  126.       cout << "DQS\n";
  127.       cout << "aa\n";
  128.       for (int ii: aa) {
  129.         cout << ii << ' ';
  130.       }
  131.       cout << "\n";
  132.     }
  133.     int piv = QuickSelect(aa);
  134.     aa = Partition(aa, piv);
  135.     if (sh) {
  136.       cout << "PERTITION DONE\n";
  137.       cout << "piv = " << piv << "\n";
  138.       cout << "aa\n";
  139.       for (int ii: aa) {
  140.         cout << ii << ' ';
  141.       }
  142.       cout << "\n\n";
  143.     }
  144.     vector<int> bb; //<piv
  145.     vector<int> cc; //==piv
  146.     vector<int> dd; //>piv
  147.     for (int ii: aa) {
  148.       if (ii < piv) {
  149.         bb.push_back(ii);
  150.       } else if (ii == piv) {
  151.         cc.push_back(ii);
  152.       } else {
  153.         dd.push_back(ii);
  154.       }
  155.     }
  156.     if (!bb.empty()) {
  157.       bb = DQS(bb);
  158.     }
  159.     if (!dd.empty()) {
  160.       dd = DQS(dd);
  161.     }
  162.     vector<int> res;
  163.     for (int ii: bb) {
  164.       res.push_back(ii);
  165.     }
  166.     for (int ii: cc) {
  167.       res.push_back(ii);
  168.     }
  169.     for (int ii: dd) {
  170.       res.push_back(ii);
  171.     }
  172.     return res;
  173.     if (sh) {
  174.       cout << "res\n";
  175.       for (int ii: res) {
  176.         cout << ii << ' ';
  177.       }
  178.       cout << "\n";
  179.     }
  180. }
  181.  
  182.  
  183.  
  184.  
  185.  
  186. int main() {
  187.   /*std::ios::sync_with_stdio(false);
  188.   std::cin.tie(0);
  189.   std::cout.tie(0);*/
  190.   int nn;
  191.   cin >> nn;
  192.   vector<int> aa(nn);
  193.   for (int& ii: aa) {
  194.     cin >> ii;
  195.   }
  196.   if (sh) {
  197.     cout << "BEGIN SORT\n";
  198.   }
  199.   aa = DQS(aa);
  200.   if (sh) {
  201.     cout << "SORTED aa\n";
  202.   }
  203.   for (int ii: aa) {
  204.     cout << ii << ' ';
  205.   }
  206.   cout << "\n";
  207. }
  208. /*
  209. 17
  210. 2 2 0 2 1 2 0 2 1 0 2 1 2 2 0 0 2
  211.  
  212. 7
  213. 10 3 4 5 11 2 1
  214. */
  215.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement