# QuickSort_v7

Sep 30th, 2023 (edited)
817
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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.