daily pastebin goal
39%
SHARE
TWEET

Untitled

a guest Aug 17th, 2017 1,256 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <cstdio>
  3. #include <iostream>
  4. #include <vector>
  5. #include <string>
  6. #include <ctime>
  7. #include <algorithm>
  8. #include <stack>
  9. #include <cassert>
  10. #include <queue>
  11. #include <map>
  12. #include <set>
  13. #include <iterator>
  14. #include <bitset>
  15. using namespace std;
  16.  
  17. template <class T>
  18. class heap {
  19. public:
  20.     int size() {
  21.         return n;
  22.     }
  23.     int top() {
  24.         return h[0];
  25.     }
  26.     bool empty() {
  27.         return n == 0;
  28.     }
  29.     void push(T a) {
  30.         h.push_back(a);
  31.         SiftUp(n);
  32.         n++;
  33.     }
  34.     void pop() {
  35.         n--;
  36.         swap(h[n], h[0]);
  37.         h.pop_back();
  38.         SiftDown(0);
  39.     }
  40.     void clear() {
  41.         h.clear();
  42.         n = 0;
  43.     }
  44.     T operator [] (int a) {
  45.         return h[a];
  46.     }
  47. private:
  48.     vector<T> h;
  49.     int n = 0;
  50.     void SiftUp(int a) {
  51.         while (a) {
  52.             int p = (a - 1) / 2;
  53.             if (h[p] > h[a]) swap(h[p], h[a]);
  54.             else break;
  55.             a--; a /= 2;
  56.         }
  57.     }
  58.     void SiftDown(int a) {
  59.         while (2 * a + 1 < n) {
  60.             int l = 2 * a + 1, r = 2 * a + 2;
  61.             if (r == n) {
  62.                 if (h[l] < h[a]) swap(h[l], h[a]);
  63.                 break;
  64.             }
  65.             else if (h[l] <= h[r]) {
  66.                 if (h[l] < h[a]) {
  67.                     swap(h[l], h[a]);
  68.                     a = l;
  69.                 }
  70.                 else break;
  71.             }
  72.             else if (h[r] < h[a]) {
  73.                 swap(h[r], h[a]);
  74.                 a = r;
  75.             }
  76.             else break;
  77.         }
  78.     }
  79. };
  80. int randint() {
  81.     return rand() * RAND_MAX + rand();
  82. }
  83. const int len[4] = { 1e5, 1e6, 1e7, 1e8 };
  84. int curt = 1;
  85.  
  86. void bubblesort(int* l, int* r) {
  87.     int sz = r - l;
  88.     if (sz <= 1) return;
  89.     bool b = true;
  90.     while (b) {
  91.         b = false;
  92.         for (int* i = l; i + 1 < r; i++) {
  93.             if (*i > *(i + 1)) {
  94.                 swap(*i, *(i + 1));
  95.                 b = true;
  96.             }
  97.         }
  98.         r--;
  99.     }
  100. }
  101. void _bubblesort(vector<int> &a, int l, int r) {
  102.     int sz = r - l;
  103.     if (sz <= 1) return;
  104.     bool b = true;
  105.     while (b) {
  106.         b = false;
  107.         for (int i = l; i < r - 1; i++) {
  108.             if (a[i] > a[i + 1]) {
  109.                 swap(a[i], a[i + 1]);
  110.                 b = true;
  111.             }
  112.         }
  113.         r--;
  114.     }
  115. }
  116. void bubblesort(vector<int> &a) {
  117.     _bubblesort(a, 0, a.size());
  118. }
  119.  
  120. void shakersort(int* l, int* r) {
  121.     int sz = r - l;
  122.     if (sz <= 1) return;
  123.     bool b = true;
  124.     int* beg = l - 1;
  125.     int* end = r - 1;
  126.     while (b) {
  127.         b = false;
  128.         beg++;
  129.         for (int* i = beg; i < end; i++) {
  130.             if (*i > *(i + 1)) {
  131.                 swap(*i, *(i + 1));
  132.                 b = true;
  133.             }
  134.         }
  135.         if (!b) break;
  136.         end--;
  137.         for (int* i = end; i > beg; i--) {
  138.             if (*i < *(i - 1)) {
  139.                 swap(*i, *(i - 1));
  140.                 b = true;
  141.             }
  142.         }
  143.     }
  144. }
  145. void _shakersort(vector<int> &a, int l, int r) {
  146.     int sz = r - l;
  147.     if (sz <= 1) return;
  148.     bool b = true;
  149.     int beg = l - 1, end = r - 1;
  150.     while (b) {
  151.         b = false;
  152.         beg++;
  153.         for (int i = beg; i < end; i++) {
  154.             if (a[i] > a[i + 1]) {
  155.                 swap(a[i], a[i + 1]);
  156.                 b = true;
  157.             }
  158.         }
  159.         if (!b) break;
  160.         end--;
  161.         for (int i = end; i > beg; i--) {
  162.             if (a[i] < a[i - 1]) {
  163.                 swap(a[i], a[i - 1]);
  164.                 b = true;
  165.             }
  166.         }
  167.     }
  168. }
  169. void shakersort(vector<int> &a) {
  170.     _shakersort(a, 0, a.size());
  171. }
  172.  
  173. void insertionsort(int* l, int* r) {
  174.     for (int *i = l + 1; i < r; i++) {
  175.         int* j = i;
  176.         while (j > l && *(j - 1) > *j) {
  177.             swap(*(j - 1), *j);
  178.             j--;
  179.         }
  180.     }
  181. }
  182. void _insertionsort(vector<int> &a, int l, int r) {
  183.     for (int i = l + 1; i < r; i++) {
  184.         int j = i;
  185.         while (j > l && a[j - 1] > a[j]) {
  186.             swap(a[j - 1], a[j]);
  187.             j--;
  188.         }
  189.     }
  190. }
  191. void insertionsort(vector<int> &a) {
  192.     _insertionsort(a, 0, a.size());
  193. }
  194.  
  195. void selectionsort(int* l, int* r) {
  196.     for (int *i = l; i < r; i++) {
  197.         int minz = *i, *ind = i;
  198.         for (int *j = i + 1; j < r; j++) {
  199.             if (*j < minz) minz = *j, ind = j;
  200.         }
  201.         swap(*i, *ind);
  202.     }
  203. }
  204. void _selectionsort(vector<int> &a, int l, int r) {
  205.     for (int i = l; i < r; i++) {
  206.         int minz = a[i], ind = i;
  207.         for (int j = i + 1; j < r; j++) {
  208.             if (minz > a[j]) minz = a[j], ind = j;
  209.         }
  210.         swap(a[i], a[ind]);
  211.     }
  212. }
  213. void selectionsort(vector<int> &a) {
  214.     _selectionsort(a, 0, a.size());
  215. }
  216.  
  217. void gnomesort(int* l, int* r) {
  218.     int *i = l;
  219.     while (i < r) {
  220.         if (i == l || *(i - 1) <= *i) i++;
  221.         else swap(*(i - 1), *i), i--;
  222.     }
  223. }
  224. void _gnomesort(vector<int> &a, int l, int r) {
  225.     int i = l;
  226.     while (i < r) {
  227.         if (i == l || a[i - 1] <= a[i]) i++;
  228.         else swap(a[i - 1], a[i]), i--;
  229.     }
  230. }
  231. void gnomesort(vector<int> &a) {
  232.     _gnomesort(a, 0, a.size());
  233. }
  234.  
  235. void combsort(int* l, int* r) {
  236.     int sz = r - l;
  237.     if (sz <= 1) return;
  238.     double k = 1.2473309;
  239.     int step = sz - 1;
  240.     while (step > 1) {
  241.         for (int* i = l; i + step < r; i++) {
  242.             if (*i > *(i + step))
  243.                 swap(*i, *(i + step));
  244.         }
  245.         step /= k;
  246.     }
  247.     bool b = true;
  248.     while (b) {
  249.         b = false;
  250.         for (int* i = l; i + 1 < r; i++) {
  251.             if (*i > *(i + 1)) {
  252.                 swap(*i, *(i + 1));
  253.                 b = true;
  254.             }
  255.         }
  256.     }
  257. }
  258. void _combsort(vector<int> &a, int l, int r) {
  259.     int sz = r - l;
  260.     if (sz <= 1) return;
  261.     double k = 1.2473309;
  262.     int step = r - l - 1;
  263.     while (step > 1) {
  264.         for (int i = l; i + step < r; i++) {
  265.             if (a[i] > a[i + step])
  266.                 swap(a[i], a[i + step]);
  267.         }
  268.         step /= k;
  269.     }
  270.     bool b = true;
  271.     while (b) {
  272.         b = false;
  273.         for (int i = l; i < r - 1; i++) {
  274.             if (a[i] > a[i + 1]) {
  275.                 swap(a[i], a[i + 1]);
  276.                 b = true;
  277.             }
  278.         }
  279.     }
  280. }
  281. void combsort(vector<int> &a) {
  282.     _combsort(a, 0, a.size());
  283. }
  284.  
  285. void shellsort(int* l, int* r) {
  286.     int sz = r - l;
  287.     int step = sz / 2;
  288.     while (step >= 1) {
  289.         for (int *i = l + step; i < r; i++) {
  290.             int *j = i;
  291.             int *diff = j - step;
  292.             while (diff >= l && *diff > *j) {
  293.                 swap(*diff, *j);
  294.                 j = diff;
  295.                 diff = j - step;
  296.             }
  297.         }
  298.         step /= 2;
  299.     }
  300. }
  301. void _shellsort(vector<int> &a, int l, int r) {
  302.     int n = r - l;
  303.     int step = n / 2;
  304.     while (step >= 1) {
  305.         for (int i = l + step; i < r; i++) {
  306.             int j = i, diff = j - step;
  307.             while (diff >= l && a[diff] > a[j]) {
  308.                 swap(a[diff], a[j]);
  309.                 j = diff;
  310.                 diff = j - step;
  311.             }
  312.         }
  313.         step /= 2;
  314.     }
  315. }
  316. void shellsort(vector<int> &a) {
  317.     _shellsort(a, 0, a.size());
  318. }
  319.  
  320. void shellsorthib(int* l, int* r) {
  321.     int sz = r - l;
  322.     if (sz <= 1) return;
  323.     int step = 1;
  324.     while (step < sz) step <<= 1;
  325.     step >>= 1;
  326.     step--;
  327.     while (step >= 1) {
  328.         for (int *i = l + step; i < r; i++) {
  329.             int *j = i;
  330.             int *diff = j - step;
  331.             while (diff >= l && *diff > *j) {
  332.                 swap(*diff, *j);
  333.                 j = diff;
  334.                 diff = j - step;
  335.             }
  336.         }
  337.         step /= 2;
  338.     }
  339. }
  340. void _shellsorthib(vector<int> &a, int l, int r) {
  341.     int n = r - l;
  342.     int step = 1;
  343.     while (step < n) step <<= 1;
  344.     step >>= 1;
  345.     while (step >= 1) {
  346.         for (int i = l + step; i < r; i++) {
  347.             int j = i, diff = j - step;
  348.             while (diff >= l && a[diff] > a[j]) {
  349.                 swap(a[diff], a[j]);
  350.                 j = diff;
  351.                 diff = j - step;
  352.             }
  353.         }
  354.         step /= 2;
  355.     }
  356. }
  357. void shellsorthib(vector<int> &a) {
  358.     _shellsorthib(a, 0, a.size());
  359. }
  360.  
  361. int steps[100];
  362. void shellsortsedgwick(int* l, int* r) {
  363.     int sz = r - l;
  364.     steps[0] = 1;
  365.     int q = 1;
  366.     while (steps[q - 1] * 3 < sz) {
  367.         if (q % 2 == 0)
  368.             steps[q] = 9 * (1 << q) - 9 * (1 << (q / 2)) + 1;
  369.         else
  370.             steps[q] = 8 * (1 << q) - 6 * (1 << ((q + 1) / 2)) + 1;
  371.         q++;
  372.     }
  373.     q--;
  374.     for (; q >= 0; q--) {
  375.         int step = steps[q];
  376.         for (int *i = l + step; i < r; i++) {
  377.             int *j = i;
  378.             int *diff = j - step;
  379.             while (diff >= l && *diff > *j) {
  380.                 swap(*diff, *j);
  381.                 j = diff;
  382.                 diff = j - step;
  383.             }
  384.         }
  385.     }
  386. }
  387. void _shellsortsedgwick(vector<int> &a, int l, int r) {
  388.     int n = r - l;
  389.     vector<int> steps;
  390.     steps.push_back(1);
  391.     int q = 1;
  392.     while (steps.back() * 3 < n) {
  393.         if (q % 2 == 0)
  394.             steps.push_back(9 * (1 << q) - 9 * (1 << (q / 2)) + 1);
  395.         else
  396.             steps.push_back(8 * (1 << q) - 6 * (1 << ((q + 1) / 2)) + 1);
  397.         q++;
  398.     }
  399.     for (int q = steps.size() - 1; q >= 0; q--) {
  400.         int step = steps[q];
  401.         for (int i = l + step; i < r; i++) {
  402.             int j = i, diff = j - step;
  403.             while (diff >= l && a[diff] > a[j]) {
  404.                 swap(a[diff], a[j]);
  405.                 j = diff;
  406.                 diff = j - step;
  407.             }
  408.         }
  409.     }
  410. }
  411. void shellsortsedgwick(vector<int> &a) {
  412.     _shellsortsedgwick(a, 0, a.size());
  413. }
  414.  
  415. void shellsortpratt(int* l, int* r) {
  416.     int sz = r - l;
  417.     steps[0] = 1;
  418.     int cur = 1, q = 1;
  419.     for (int i = 1; i < sz; i++) {
  420.         int cur = 1 << i;
  421.         if (cur > sz / 2) break;
  422.         for (int j = 1; j < sz; j++) {
  423.             cur *= 3;
  424.             if (cur > sz / 2) break;
  425.             steps[q++] = cur;
  426.         }
  427.     }
  428.     insertionsort(steps, steps + q);
  429.     q--;
  430.     for (; q >= 0; q--) {
  431.         int step = steps[q];
  432.         for (int *i = l + step; i < r; i++) {
  433.             int *j = i;
  434.             int *diff = j - step;
  435.             while (diff >= l && *diff > *j) {
  436.                 swap(*diff, *j);
  437.                 j = diff;
  438.                 diff = j - step;
  439.             }
  440.         }
  441.     }
  442. }
  443. void _shellsortpratt(vector<int> &a, int l, int r) {
  444.     int n = r - l;
  445.     vector<int> steps;
  446.     steps.push_back(1);
  447.     int cur = 1;
  448.     for (int i = 1; i < n; i++) {
  449.         int cur = 1 << i;
  450.         if (cur > n / 2) break;
  451.         for (int j = 1; j < n; j++) {
  452.             cur *= 3;
  453.             if (cur > n / 2) break;
  454.             steps.push_back(cur);
  455.         }
  456.     }
  457.     sort(steps.begin(), steps.end());
  458.     for (int q = steps.size() - 1; q >= 0; q--) {
  459.         int step = steps[q];
  460.         for (int i = l + step; i < r; i++) {
  461.             int j = i, diff = j - step;
  462.             while (diff >= l && a[diff] > a[j]) {
  463.                 swap(a[diff], a[j]);
  464.                 j = diff;
  465.                 diff = j - step;
  466.             }
  467.         }
  468.     }
  469. }
  470. void shellsortpratt(vector<int> &a) {
  471.     _shellsortpratt(a, 0, a.size());
  472. }
  473.  
  474. void myshell1(int* l, int* r) {
  475.     int sz = r - l, q = 1;
  476.     steps[0] = 1;
  477.     while (steps[q - 1] < sz) {
  478.         int s = steps[q - 1];
  479.         steps[q++] = s * 4 + s / 4;
  480.     }
  481.     q--;
  482.     for (; q >= 0; q--) {
  483.         int step = steps[q];
  484.         for (int *i = l + step; i < r; i++) {
  485.             int *j = i;
  486.             int *diff = j - step;
  487.             while (diff >= l && *diff > *j) {
  488.                 swap(*diff, *j);
  489.                 j = diff;
  490.                 diff = j - step;
  491.             }
  492.         }
  493.     }
  494. }
  495. void _myshell1(vector<int> &a, int l, int r) {
  496.     int n = r - l;
  497.     vector<int> steps;
  498.     steps.push_back(1);
  499.     while (steps.back() < n) {
  500.         int s = steps.back();
  501.         steps.push_back(s * 4 + s / 4);
  502.     }
  503.     for (int q = steps.size() - 1; q >= 0; q--) {
  504.         int step = steps[q];
  505.         for (int i = l + step; i < r; i++) {
  506.             int j = i, diff = j - step;
  507.             while (diff >= l && a[diff] > a[j]) {
  508.                 swap(a[diff], a[j]);
  509.                 j = diff;
  510.                 diff = j - step;
  511.             }
  512.         }
  513.     }
  514. }
  515. void myshell1(vector<int> &a) {
  516.     _myshell1(a, 0, a.size());
  517. }
  518.  
  519. void myshell2(int* l, int* r) {
  520.     int sz = r - l, q = 1;
  521.     steps[0] = 1;
  522.     while (steps[q - 1] < sz) {
  523.         int s = steps[q - 1];
  524.         steps[q++] = s * 3 + s / 3;
  525.     }
  526.     q--;
  527.     for (; q >= 0; q--) {
  528.         int step = steps[q];
  529.         for (int *i = l + step; i < r; i++) {
  530.             int *j = i;
  531.             int *diff = j - step;
  532.             while (diff >= l && *diff > *j) {
  533.                 swap(*diff, *j);
  534.                 j = diff;
  535.                 diff = j - step;
  536.             }
  537.         }
  538.     }
  539. }
  540. void _myshell2(vector<int> &a, int l, int r) {
  541.     int n = r - l;
  542.     vector<int> steps;
  543.     steps.push_back(1);
  544.     while (steps.back() < n) {
  545.         int s = steps.back();
  546.         steps.push_back(s * 3 + s / 3);
  547.     }
  548.     for (int q = steps.size() - 1; q >= 0; q--) {
  549.         int step = steps[q];
  550.         for (int i = l + step; i < r; i++) {
  551.             int j = i, diff = j - step;
  552.             while (diff >= l && a[diff] > a[j]) {
  553.                 swap(a[diff], a[j]);
  554.                 j = diff;
  555.                 diff = j - step;
  556.             }
  557.         }
  558.     }
  559. }
  560. void myshell2(vector<int> &a) {
  561.     _myshell2(a, 0, a.size());
  562. }
  563.  
  564. void myshell3(int* l, int* r) {
  565.     int sz = r - l, q = 1;
  566.     steps[0] = 1;
  567.     while (steps[q - 1] < sz) {
  568.         int s = steps[q - 1];
  569.         steps[q++] = s * 4 - s / 5;
  570.     }
  571.     q--;
  572.     for (; q >= 0; q--) {
  573.         int step = steps[q];
  574.         for (int *i = l + step; i < r; i++) {
  575.             int *j = i;
  576.             int *diff = j - step;
  577.             while (diff >= l && *diff > *j) {
  578.                 swap(*diff, *j);
  579.                 j = diff;
  580.                 diff = j - step;
  581.             }
  582.         }
  583.     }
  584. }
  585. void _myshell3(vector<int> &a, int l, int r) {
  586.     int n = r - l;
  587.     vector<int> steps;
  588.     steps.push_back(1);
  589.     while (steps.back() < n) {
  590.         int s = steps.back();
  591.         steps.push_back(s * 4 - s / 5);
  592.     }
  593.     for (int q = steps.size() - 1; q >= 0; q--) {
  594.         int step = steps[q];
  595.         for (int i = l + step; i < r; i++) {
  596.             int j = i, diff = j - step;
  597.             while (diff >= l && a[diff] > a[j]) {
  598.                 swap(a[diff], a[j]);
  599.                 j = diff;
  600.                 diff = j - step;
  601.             }
  602.         }
  603.     }
  604. }
  605. void myshell3(vector<int> &a) {
  606.     _myshell3(a, 0, a.size());
  607. }
  608.  
  609. void quicksort(int* l, int* r) {
  610.     if (r - l <= 1) return;
  611.     int z = *(l + (r - l) / 2);
  612.     int* ll = l, *rr = r - 1;
  613.     while (ll <= rr) {
  614.         while (*ll < z) ll++;
  615.         while (*rr > z) rr--;
  616.         if (ll <= rr) {
  617.             swap(*ll, *rr);
  618.             ll++;
  619.             rr--;
  620.         }
  621.     }
  622.     if (l < rr) quicksort(l, rr + 1);
  623.     if (ll < r) quicksort(ll, r);
  624. }
  625. void _quicksort(vector<int> &a, int l, int r) {
  626.     if (r - l <= 1) return;
  627.     int z = a[(l + r) / 2];
  628.     int ll = l, rr = r - 1;
  629.     while (ll <= rr) {
  630.         while (a[ll] < z) ll++;
  631.         while (a[rr] > z) rr--;
  632.         if (ll <= rr) swap(a[ll++], a[rr--]);
  633.     }
  634.     if (l < rr) _quicksort(a, l, rr + 1);
  635.     if (ll < r) _quicksort(a, ll, r);
  636. }
  637. void quicksort(vector<int> &a) {
  638.     _quicksort(a, 0, a.size());
  639. }
  640.  
  641. void quickinssort(int* l, int* r) {
  642.     if (r - l <= 32) {
  643.         insertionsort(l, r);
  644.         return;
  645.     }
  646.     int z = *(l + (r - l) / 2);
  647.     int* ll = l, *rr = r - 1;
  648.     while (ll <= rr) {
  649.         while (*ll < z) ll++;
  650.         while (*rr > z) rr--;
  651.         if (ll <= rr) {
  652.             swap(*ll, *rr);
  653.             ll++;
  654.             rr--;
  655.         }
  656.     }
  657.     if (l < rr) quickinssort(l, rr + 1);
  658.     if (ll < r) quickinssort(ll, r);
  659. }
  660. void _quickinssort(vector<int> &a, int l, int r) {
  661.     if (r - l <= 32) {
  662.         _insertionsort(a, l, r);
  663.         return;
  664.     }
  665.     int z = a[(l + r) / 2];
  666.     int ll = l, rr = r - 1;
  667.     while (ll <= rr) {
  668.         while (a[ll] < z) ll++;
  669.         while (a[rr] > z) rr--;
  670.         if (ll <= rr) swap(a[ll++], a[rr--]);
  671.     }
  672.     if (l < rr) _quickinssort(a, l, rr + 1);
  673.     if (ll < r) _quickinssort(a, ll, r);
  674. }
  675. void quickinssort(vector<int> &a) {
  676.     _quickinssort(a, 0, a.size());
  677. }
  678.  
  679. void heapsort(int* l, int* r) {
  680.     heap<int> h;
  681.     for (int *i = l; i < r; i++) h.push(*i);
  682.     for (int *i = l; i < r; i++) {
  683.         *i = h.top();
  684.         h.pop();
  685.     }
  686. }
  687. void _heapsort(vector<int> &a, int l, int r) {
  688.     heap<int> h;
  689.     for (int i = l; i < r; i++) h.push(a[i]);
  690.     for (int i = l; i < r; i++) {
  691.         a[i] = h.top();
  692.         h.pop();
  693.     }
  694. }
  695. void heapsort(vector<int> &a) {
  696.     _heapsort(a, 0, a.size());
  697. }
  698.  
  699. void merge(int* l, int* m, int* r, int* temp) {
  700.     int *cl = l, *cr = m, cur = 0;
  701.     while (cl < m && cr < r) {
  702.         if (*cl < *cr) temp[cur++] = *cl, cl++;
  703.         else temp[cur++] = *cr, cr++;
  704.     }
  705.     while (cl < m) temp[cur++] = *cl, cl++;
  706.     while (cr < r) temp[cur++] = *cr, cr++;
  707.     cur = 0;
  708.     for (int* i = l; i < r; i++)
  709.          *i = temp[cur++];
  710. }
  711. void _mergesort(int* l, int* r, int* temp) {
  712.     if (r - l <= 1) return;
  713.     int *m = l + (r - l) / 2;
  714.     _mergesort(l, m, temp);
  715.     _mergesort(m, r, temp);
  716.     merge(l, m, r, temp);
  717. }
  718. void mergesort(int* l, int* r) {
  719.     int* temp = new int[r - l];
  720.     _mergesort(l, r, temp);
  721.     delete temp;
  722. }
  723. void merge(vector<int> &a, int l, int r, int* temp) {
  724.     int m = (l + r) / 2;
  725.     int cl = l, cr = m, cur = 0;
  726.     while (cl < m && cr < r) {
  727.         if (a[cl] < a[cr]) temp[cur++] = a[cl++];
  728.         else temp[cur++] = a[cr++];
  729.     }
  730.     while (cl < m) temp[cur++] = a[cl++];
  731.     while (cr < r) temp[cur++] = a[cr++];
  732.     for (int i = 0; i < r - l; i++)
  733.         a[i + l] = temp[i];
  734. }
  735. void _mergesort(vector<int> &a, int l, int r, int* temp) {
  736.     if (l >= r - 1) return;
  737.     int m = (l + r) / 2;
  738.     _mergesort(a, l, m, temp);
  739.     _mergesort(a, m, r, temp);
  740.     merge(a, l, r, temp);
  741. }
  742. void mergesort(vector<int> &a) {
  743.     int* temp = new int[a.size()];
  744.     _mergesort(a, 0, a.size(), temp);
  745.     delete temp;
  746. }
  747.  
  748. void _mergeinssort(int* l, int* r, int* temp) {
  749.     if (r - l <= 32) {
  750.         insertionsort(l, r);
  751.         return;
  752.     }
  753.     int *m = l + (r - l) / 2;
  754.     _mergeinssort(l, m, temp);
  755.     _mergeinssort(m, r, temp);
  756.     merge(l, m, r, temp);
  757. }
  758. void mergeinssort(int* l, int* r) {
  759.     int* temp = new int[r - l];
  760.     _mergeinssort(l, r, temp);
  761.     delete temp;
  762. }
  763. void _mergeinssort(vector<int> &a, int l, int r, int* temp) {
  764.     if (r - l <= 64) {
  765.         _insertionsort(a, l, r);
  766.         return;
  767.     }
  768.     int m = (l + r) / 2;
  769.     _mergeinssort(a, l, m, temp);
  770.     _mergeinssort(a, m, r, temp);
  771.     merge(a, l, r, temp);
  772. }
  773. void mergeinssort(vector<int> &a) {
  774.     int* temp = new int[a.size()];
  775.     _mergeinssort(a, 0, a.size(), temp);
  776.     delete temp;
  777. }
  778.  
  779. int digit(int n, int k, int N, int M) {
  780.     return (n >> (N * k) & (M - 1));
  781. }
  782. void _radixsort(int* l, int* r, int N) {
  783.     int k = (32 + N - 1) / N;
  784.     int M = 1 << N;
  785.     int sz = r - l;
  786.     int* b = new int[sz];
  787.     int* c = new int[M];
  788.     for (int i = 0; i < k; i++) {
  789.         for (int j = 0; j < M; j++)
  790.             c[j] = 0;
  791.         for (int* j = l; j < r; j++)
  792.             c[digit(*j, i, N, M)]++;
  793.         for (int j = 1; j < M; j++)
  794.             c[j] += c[j - 1];
  795.         for (int* j = r - 1; j >= l; j--)
  796.             b[--c[digit(*j, i, N, M)]] = *j;
  797.         int cur = 0;
  798.         for (int* j = l; j < r; j++)
  799.             *j = b[cur++];
  800.     }
  801.     delete b;
  802.     delete c;
  803. }
  804. void radixsort(int* l, int* r) {
  805.     _radixsort(l, r, 8);
  806. }
  807. void _radixsort(vector<int> &a, int N) {
  808.     int k = (32 + N - 1) / N;
  809.     int M = 1 << N;
  810.     int n = a.size();
  811.     vector<int> b(n);
  812.     for (int i = 0; i < k; i++) {
  813.         vector<int> c(M);
  814.         for (int j = 0; j < n; j++)
  815.             c[digit(a[j], i, N, M)]++;
  816.         for (int j = 1; j < M; j++)
  817.             c[j] += c[j - 1];
  818.         for (int j = n - 1; j >= 0; j--)
  819.             b[--c[digit(a[j], i, N, M)]] = a[j];
  820.         swap(a, b);
  821.     }
  822. }
  823. void radixsort(vector<int> &a) {
  824.     _radixsort(a, 8);
  825. }
  826.  
  827. void _radixsortmsd(int* l, int* r, int N, int d, int* temp) {
  828.     if (d == -1) return;
  829.     if (r - l <= 32) {
  830.         insertionsort(l, r);
  831.         return;
  832.     }
  833.     int M = 1 << N;
  834.     int* cnt = new int[M + 1];
  835.     for (int i = 0; i <= M; i++)
  836.         cnt[i] = 0;
  837.     int cur = 0;
  838.     for (int* i = l; i < r; i++) {
  839.         temp[cur++] = *i;
  840.         cnt[digit(*i, d, N, M) + 1]++;
  841.     }
  842.     int sz = 0;
  843.     for (int i = 1; i <= M; i++)
  844.         if (cnt[i]) sz++;
  845.     int* run = new int[sz];
  846.     cur = 0;
  847.     for (int i = 1; i <= M; i++)
  848.         if (cnt[i]) run[cur++] = i - 1;
  849.     for (int i = 1; i <= M; i++)
  850.         cnt[i] += cnt[i - 1];
  851.     cur = 0;
  852.     for (int *i = l; i < r; i++) {
  853.         int ind = digit(temp[cur], d, N, M);
  854.         *(l + cnt[ind]) = temp[cur];
  855.         cur++;
  856.         cnt[ind]++;
  857.     }
  858.     for (int i = 0; i < sz; i++) {
  859.         int r = run[i];
  860.         if (r != 0) _radixsortmsd(l + cnt[r - 1], l + cnt[r], N, d - 1, temp);
  861.         else _radixsortmsd(l, l + cnt[r], N, d - 1, temp);
  862.     }
  863.     delete run;
  864.     delete cnt;
  865. }
  866. void radixsortmsd(int* l, int* r) {
  867.     int* temp = new int[r - l];
  868.     _radixsortmsd(l, r, 8, 3, temp);
  869.     delete temp;
  870. }
  871.  
  872. void _radixsortmsd(vector<int> &a, int N, int d) {
  873.     if (d == -1 || a.size() <= 1) return;
  874.     if (a.size() <= 64) {
  875.         insertionsort(a);
  876.         return;
  877.     }
  878.     int k = (32 + N - 1) / N;
  879.     int M = 1 << N;
  880.     int n = a.size();
  881.     vector<vector<int>> c(M);
  882.     for (int i = 0; i < n; i++)
  883.         c[digit(a[i], d, N, M)].push_back(a[i]);
  884.     for (int i = 0; i < M; i++)
  885.         _radixsortmsd(c[i], N, d - 1);
  886.     int cur = 0;
  887.     for (int i = 0; i < M; i++)
  888.         for (int j = 0; j < c[i].size(); j++)
  889.             a[cur++] = c[i][j];
  890. }
  891. void radixsortmsd(vector<int> &a) {
  892.     _radixsortmsd(a, 4, 7);
  893. }
  894.  
  895. void _stlsort(vector<int> &a, int l, int r) {
  896.     sort(a.begin() + l, a.begin() + r);
  897. }
  898. void stlsort(vector<int> &a) {
  899.     sort(a.begin(), a.end());
  900. }
  901.  
  902. void _timsort(int* l, int* r, int* temp) {
  903.     int sz = r - l;
  904.     if (sz <= 64) {
  905.         insertionsort(l, r);
  906.         return;
  907.     }
  908.     int minrun = sz, f = 0;
  909.     while (minrun >= 64) {
  910.         f |= minrun & 1;
  911.         minrun >>= 1;
  912.     }
  913.     minrun += f;
  914.     int* cur = l;
  915.     stack<pair<int, int*>> s;
  916.     while (cur < r) {
  917.         int* c1 = cur;
  918.         while (c1 < r - 1 && *c1 <= *(c1 + 1)) c1++;
  919.         int* c2 = cur;
  920.         while (c2 < r - 1 && *c2 >= *(c2 + 1)) c2++;
  921.         if (c1 >= c2) {
  922.             c1 = max(c1, cur + minrun - 1);
  923.             c1 = min(c1, r - 1);
  924.             insertionsort(cur, c1 + 1);
  925.             s.push({ c1 - cur + 1, cur });
  926.             cur = c1 + 1;
  927.         }
  928.         else {
  929.             c2 = max(c2, cur + minrun - 1);
  930.             c2 = min(c2, r - 1);
  931.             reverse(cur, c2 + 1);
  932.             insertionsort(cur, c2 + 1);
  933.             s.push({ c2 - cur + 1, cur });
  934.             cur = c2 + 1;
  935.         }
  936.         while (s.size() >= 3) {
  937.             pair<int, int*> x = s.top();
  938.             s.pop();
  939.             pair<int, int*> y = s.top();
  940.             s.pop();
  941.             pair<int, int*> z = s.top();
  942.             s.pop();
  943.             if (z.first >= x.first + y.first && y.first >= x.first) {
  944.                 s.push(z);
  945.                 s.push(y);
  946.                 s.push(x);
  947.                 break;
  948.             }
  949.             else if (z.first >= x.first + y.first) {
  950.                 merge(y.second, x.second, x.second + x.first, temp);
  951.                 s.push(z);
  952.                 s.push({ x.first + y.first, y.second });
  953.             }
  954.             else {
  955.                 merge(z.second, y.second, y.second + y.first, temp);
  956.                 s.push({ z.first + y.first, z.second });
  957.                 s.push(x);
  958.             }
  959.         }
  960.     }
  961.     while (s.size() != 1) {
  962.         pair<int, int*> x = s.top();
  963.         s.pop();
  964.         pair<int, int*> y = s.top();
  965.         s.pop();
  966.         if (x.second < y.second) swap(x, y);
  967.         merge(y.second, x.second, x.second + x.first, temp);
  968.         s.push({ y.first + x.first, y.second });
  969.     }
  970. }
  971. void timsort(int* l, int* r) {
  972.     int* temp = new int[r - l];
  973.     _timsort(l, r, temp);
  974.     delete temp;
  975. }
  976.  
  977. void mergetim(vector<int> &a, int l, int m, int r, int* temp) {
  978.     int cl = l, cr = m, cur = 0;
  979.     while (cl < m && cr < r) {
  980.         if (a[cl] < a[cr]) temp[cur++] = a[cl++];
  981.         else temp[cur++] = a[cr++];
  982.     }
  983.     while (cl < m) temp[cur++] = a[cl++];
  984.     while (cr < r) temp[cur++] = a[cr++];
  985.     for (int i = 0; i < r - l; i++)
  986.         a[i + l] = temp[i];
  987. }
  988. void _timsort(vector<int> &a, int l, int r, int* temp) {
  989.     int sz = r - l;
  990.     if (sz <= 64) {
  991.         _insertionsort(a, l, r);
  992.         return;
  993.     }
  994.     int minrun = sz, f = 0;
  995.     while (minrun >= 64) {
  996.         f |= minrun & 1;
  997.         minrun >>= 1;
  998.     }
  999.     minrun += f;
  1000.     int cur = l;
  1001.     stack<pair<int, int>> s;
  1002.     while (cur < r) {
  1003.         int c1 = cur;
  1004.         while (c1 < r - 1 && a[c1] <= a[c1 + 1]) c1++;
  1005.         int c2 = cur;
  1006.         while (c2 < r - 1 && a[c2] >= a[c2 + 1]) c2++;
  1007.         if (c1 >= c2) {
  1008.             c1 = max(c1, cur + minrun - 1);
  1009.             c1 = min(c1, r - 1);
  1010.             _insertionsort(a, cur, c1 + 1);
  1011.             s.push({ c1 - cur + 1, cur });
  1012.             cur = c1 + 1;
  1013.         }
  1014.         else {
  1015.             c2 = max(c2, cur + minrun - 1);
  1016.             c2 = min(c2, r - 1);
  1017.             reverse(a.begin() + cur, a.begin() + c2 + 1);
  1018.             _insertionsort(a, cur, c2 + 1);
  1019.             s.push({ c2 - cur + 1, cur });
  1020.             cur = c2 + 1;
  1021.         }
  1022.         while (s.size() >= 3) {
  1023.             pair<int, int> x = s.top();
  1024.             s.pop();
  1025.             pair<int, int> y = s.top();
  1026.             s.pop();
  1027.             pair<int, int> z = s.top();
  1028.             s.pop();
  1029.             if (z.first >= x.first + y.first && y.first >= x.first) {
  1030.                 s.push(z);
  1031.                 s.push(y);
  1032.                 s.push(x);
  1033.                 break;
  1034.             }
  1035.             else if (z.first >= x.first + y.first) {
  1036.                 mergetim(a, y.second, x.second, x.second + x.first, temp);
  1037.                 s.push(z);
  1038.                 s.push({ x.first + y.first, y.second });
  1039.             }
  1040.             else {
  1041.                 mergetim(a, z.second, y.second, y.second + y.first, temp);
  1042.                 s.push({ z.first + y.first, z.second });
  1043.                 s.push(x);
  1044.             }
  1045.         }
  1046.     }
  1047.     while (s.size() != 1) {
  1048.         pair<int, int> x = s.top();
  1049.         s.pop();
  1050.         pair<int, int> y = s.top();
  1051.         s.pop();
  1052.         if (x.second < y.second) swap(x, y);
  1053.         mergetim(a, y.second, x.second, x.second + x.first, temp);
  1054.         s.push({ y.first + x.first, y.second });
  1055.     }
  1056. }
  1057. void timsort(vector<int> &a) {
  1058.     int* temp = new int[a.size()];
  1059.     _timsort(a, 0, a.size(), temp);
  1060.     delete temp;
  1061. }
  1062.  
  1063. void bucketinssort(vector<int> &a);
  1064. void _bucketinssort(vector<int> &a, int l, int r) {
  1065.     int sz = r - l;
  1066.     if (sz <= 128) {
  1067.         _insertionsort(a, l, r);
  1068.         return;
  1069.     }
  1070.     int minz = a[0], maxz = a[0];
  1071.     for (int i = l; i < r; i++) {
  1072.         minz = min(minz, a[i]);
  1073.         maxz = max(maxz, a[i]);
  1074.     }
  1075.     int diff = maxz - minz + 1;
  1076.     if (diff == 1) return;
  1077.     int numbuckets;
  1078.     numbuckets = max(2, int(4 * log2(diff)));
  1079.     vector<vector<int>> buckets(numbuckets);
  1080.     int range = (diff + numbuckets - 1) / numbuckets;
  1081.     for (int i = l; i < r; i++) {
  1082.         int ind = (a[i] - minz) / range;
  1083.         buckets[ind].push_back(a[i]);
  1084.     }
  1085.     for (int i = 0; i < numbuckets; i++)
  1086.         bucketinssort(buckets[i]);
  1087.     int cur = l;
  1088.     for (int i = 0; i < numbuckets; i++)
  1089.         for (int j = 0; j < buckets[i].size(); j++)
  1090.             a[cur++] = buckets[i][j];
  1091. }
  1092. void bucketinssort(vector<int> &a) {
  1093.     _bucketinssort(a, 0, a.size());
  1094. }
  1095. void bucketquicksort(vector<int> &a);
  1096. void _bucketquicksort(vector<int> &a, int l, int r) {
  1097.     int sz = r - l;
  1098.     if (sz <= 10000) {
  1099.         _quicksort(a, l, r);
  1100.         return;
  1101.     }
  1102.     int minz = a[0], maxz = a[0];
  1103.     for (int i = l; i < r; i++) {
  1104.         minz = min(minz, a[i]);
  1105.         maxz = max(maxz, a[i]);
  1106.     }
  1107.     int diff = maxz - minz + 1;
  1108.     if (diff == 1) return;
  1109.     int numbuckets;
  1110.     numbuckets = max(2, int(4 * log2(diff)));
  1111.     vector<vector<int>> buckets(numbuckets);
  1112.     int range = (diff + numbuckets - 1) / numbuckets;
  1113.     for (int i = l; i < r; i++) {
  1114.         int ind = (a[i] - minz) / range;
  1115.         buckets[ind].push_back(a[i]);
  1116.     }
  1117.     for (int i = 0; i < numbuckets; i++)
  1118.         bucketquicksort(buckets[i]);
  1119.     int cur = l;
  1120.     for (int i = 0; i < numbuckets; i++)
  1121.         for (int j = 0; j < buckets[i].size(); j++)
  1122.             a[cur++] = buckets[i][j];
  1123. }
  1124. void bucketquicksort(vector<int> &a) {
  1125.     _bucketquicksort(a, 0, a.size());
  1126. }
  1127. void bucketquickinssort(vector<int> &a);
  1128. void _bucketquickinssort(vector<int> &a, int l, int r) {
  1129.     int sz = r - l;
  1130.     if (sz <= 10000) {
  1131.         _quickinssort(a, l, r);
  1132.         return;
  1133.     }
  1134.     int minz = a[0], maxz = a[0];
  1135.     for (int i = l; i < r; i++) {
  1136.         minz = min(minz, a[i]);
  1137.         maxz = max(maxz, a[i]);
  1138.     }
  1139.     int diff = maxz - minz + 1;
  1140.     if (diff == 1) return;
  1141.     int numbuckets;
  1142.     numbuckets = max(2, int(4 * log2(diff)));
  1143.     vector<vector<int>> buckets(numbuckets);
  1144.     int range = (diff + numbuckets - 1) / numbuckets;
  1145.     for (int i = l; i < r; i++) {
  1146.         int ind = (a[i] - minz) / range;
  1147.         buckets[ind].push_back(a[i]);
  1148.     }
  1149.     for (int i = 0; i < numbuckets; i++)
  1150.         bucketquickinssort(buckets[i]);
  1151.     int cur = l;
  1152.     for (int i = 0; i < numbuckets; i++)
  1153.         for (int j = 0; j < buckets[i].size(); j++)
  1154.             a[cur++] = buckets[i][j];
  1155. }
  1156. void bucketquickinssort(vector<int> &a) {
  1157.     _bucketquickinssort(a, 0, a.size());
  1158. }
  1159.  
  1160. void _newbucketsort(int* l, int* r, int* temp) {
  1161.     if (r - l <= 64) {
  1162.         insertionsort(l, r);
  1163.         return;
  1164.     }
  1165.     int minz = *l, maxz = *l;
  1166.     bool is_sorted = true;
  1167.     for (int *i = l + 1; i < r; i++) {
  1168.         minz = min(minz, *i);
  1169.         maxz = max(maxz, *i);
  1170.         if (*i < *(i - 1)) is_sorted = false;
  1171.     }
  1172.     if (is_sorted) return;
  1173.     int diff = maxz - minz + 1;
  1174.     int numbuckets;
  1175.     if (r - l <= 1e7) numbuckets = 1500;
  1176.     else numbuckets = 3000;
  1177.     int range = (diff + numbuckets - 1) / numbuckets;
  1178.     int* cnt = new int[numbuckets + 1];
  1179.     for (int i = 0; i <= numbuckets; i++)
  1180.         cnt[i] = 0;
  1181.     int cur = 0;
  1182.     for (int* i = l; i < r; i++) {
  1183.         temp[cur++] = *i;
  1184.         int ind = (*i - minz) / range;
  1185.         cnt[ind + 1]++;
  1186.     }
  1187.     int sz = 0;
  1188.     for (int i = 1; i <= numbuckets; i++)
  1189.         if (cnt[i]) sz++;
  1190.     int* run = new int[sz];
  1191.     cur = 0;
  1192.     for (int i = 1; i <= numbuckets; i++)
  1193.         if (cnt[i]) run[cur++] = i - 1;
  1194.     for (int i = 1; i <= numbuckets; i++)
  1195.         cnt[i] += cnt[i - 1];
  1196.     cur = 0;
  1197.     for (int *i = l; i < r; i++) {
  1198.         int ind = (temp[cur] - minz) / range;
  1199.         *(l + cnt[ind]) = temp[cur];
  1200.         cur++;
  1201.         cnt[ind]++;
  1202.     }
  1203.     for (int i = 0; i < sz; i++) {
  1204.         int r = run[i];
  1205.         if (r != 0) _newbucketsort(l + cnt[r - 1], l + cnt[r], temp);
  1206.         else _newbucketsort(l, l + cnt[r], temp);
  1207.     }
  1208.     delete run;
  1209.     delete cnt;
  1210. }
  1211. void newbucketsort(int* l, int* r) {
  1212.     int *temp = new int[r - l];
  1213.     _newbucketsort(l, r, temp);
  1214.     delete temp;
  1215. }
  1216. void _newbucketsort(vector<int> &a, int l, int r, int* temp) {
  1217.     if (r - l <= 64) {
  1218.         _insertionsort(a, l, r);
  1219.         return;
  1220.     }
  1221.     int minz = a[l], maxz = a[l];
  1222.     bool is_sorted = true;
  1223.     for (int i = l + 1; i < r; i++) {
  1224.         minz = min(minz, a[i]);
  1225.         maxz = max(maxz, a[i]);
  1226.         if (a[i] < a[i - 1]) is_sorted = false;
  1227.     }
  1228.     if (is_sorted) return;
  1229.     int diff = maxz - minz + 1;
  1230.     int numbuckets = 1500;
  1231.     //numbuckets = min(diff, int(4.0 * log2(diff)));
  1232.     //numbuckets = min(diff, int(6.0 * log2(r - l)));
  1233.     //numbuckets = min(diff, min(int(4.0 * log2(diff)),
  1234.     //  int(6.0 * log2(r - l))));
  1235.     int range = (diff + numbuckets - 1) / numbuckets;
  1236.     vector<int> cnt(numbuckets + 1);
  1237.     cnt[0] = l;
  1238.     for (int i = l; i < r; i++) {
  1239.         temp[i] = a[i];
  1240.         int ind = (a[i] - minz) / range;
  1241.         cnt[ind + 1]++;
  1242.     }
  1243.     vector<int> run;
  1244.     int sz = 0;
  1245.     for (int i = 1; i <= numbuckets; i++)
  1246.         if (cnt[i]) sz++;
  1247.     run.resize(sz);
  1248.     int cur = 0;
  1249.     for (int i = 1; i <= numbuckets; i++)
  1250.         if (cnt[i]) run[cur++] = i - 1;
  1251.     for (int i = 1; i <= numbuckets; i++)
  1252.         cnt[i] += cnt[i - 1];
  1253.     for (int i = l; i < r; i++) {
  1254.         int ind = (temp[i] - minz) / range;
  1255.         a[cnt[ind]++] = temp[i];
  1256.     }
  1257.     for (int i = 0; i < sz; i++) {
  1258.         int r = run[i];
  1259.         if (r != 0) _newbucketsort(a, cnt[r - 1], cnt[r], temp);
  1260.         else _newbucketsort(a, l, cnt[r], temp);
  1261.     }
  1262. }
  1263. void newbucketsort(vector<int> &a) {
  1264.     int *temp = new int[a.size()];
  1265.     _newbucketsort(a, 0, a.size(), temp);
  1266.     delete temp;
  1267. }
  1268.  
  1269. void treesort(int* l, int* r) {
  1270.     multiset<int> m;
  1271.     for (int *i = l; i < r; i++)
  1272.         m.insert(*i);
  1273.     for (int q : m)
  1274.         *l = q, l++;
  1275. }
  1276. void _treesort(vector<int> &a, int l, int r) {
  1277.     multiset<int> m;
  1278.     for (int i = l; i < r; i++)
  1279.         m.insert(a[i]);
  1280.     int cur = l;
  1281.     for (int q : m)
  1282.         a[cur++] = q;
  1283. }
  1284. void treesort(vector<int> &a) {
  1285.     _treesort(a, 0, a.size());
  1286. }
  1287.  
  1288. void bitseqsort(int* l, int* r, bool inv) {
  1289.     if (r - l <= 1) return;
  1290.     int *m = l + (r - l) / 2;
  1291.     for (int *i = l, *j = m; i < m && j < r; i++, j++) {
  1292.         if (inv ^ (*i > *j)) swap(*i, *j);
  1293.     }
  1294.     bitseqsort(l, m, inv);
  1295.     bitseqsort(m, r, inv);
  1296. }
  1297. void makebitonic(int* l, int* r) {
  1298.     if (r - l <= 1) return;
  1299.     int *m = l + (r - l) / 2;
  1300.     makebitonic(l, m);
  1301.     bitseqsort(l, m, 0);
  1302.     makebitonic(m, r);
  1303.     bitseqsort(m, r, 1);
  1304. }
  1305. void bitonicsort(int* l, int* r) {
  1306.     int n = 1;
  1307.     int inf = *max_element(l, r) + 1;
  1308.     while (n < r - l) n *= 2;
  1309.     int* a = new int[n];
  1310.     int cur = 0;
  1311.     for (int *i = l; i < r; i++)
  1312.         a[cur++] = *i;
  1313.     while (cur < n) a[cur++] = inf;
  1314.     makebitonic(a, a + n);
  1315.     bitseqsort(a, a + n, 0);
  1316.     cur = 0;
  1317.     for (int *i = l; i < r; i++)
  1318.         *i = a[cur++];
  1319.     delete a;
  1320. }
  1321. void bitseqsort(vector<int> &a, int l, int r, bool inv) {
  1322.     if (l == r - 1) return;
  1323.     int m = (l + r) / 2;
  1324.     for (int i = l, j = m; i < m && j < r; i++, j++) {
  1325.         if (inv ^ (a[i] > a[j])) swap(a[i], a[j]);
  1326.     }
  1327.     bitseqsort(a, l, m, inv);
  1328.     bitseqsort(a, m, r, inv);
  1329. }
  1330. void makebitonic(vector<int> &a, int l, int r) {
  1331.     if (r - l <= 1) return;
  1332.     int m = (l + r) / 2;
  1333.     makebitonic(a, l, m);
  1334.     bitseqsort(a, l, m, 0);
  1335.     makebitonic(a, m, r);
  1336.     bitseqsort(a, m, r, 1);
  1337. }
  1338. void bitonicsort(vector<int> &a) {
  1339.     int n = 1;
  1340.     int inf = *max_element(a.begin(), a.end()) + 1;
  1341.     while (n < a.size()) n *= 2;
  1342.     a.resize(n, inf);
  1343.     makebitonic(a, 0, n);
  1344.     bitseqsort(a, 0, n, 0);
  1345.     while (a.back() == inf && !a.empty()) a.pop_back();
  1346. }
  1347.  
  1348. /*void(*func1[5])(vector<int>&) =
  1349. { bubblesort, gnomesort, insertionsort, selectionsort, shakersort };
  1350. string names1[5] =
  1351. { "bubblesort", "gnomesort", "insertionsort", "selectionsort", "shakersort" };
  1352. void(*func2[4])(vector<int>&) =
  1353. { bitonicsort, shellsorthib, shellsortpratt, treesort };
  1354. string names2[4] =
  1355. { "bitonicsort", "shellsorthib", "shellsortpratt", "treesort" };
  1356. void(*func3[18])(vector<int>&) =
  1357. { combsort, bucketinssort, heapsort, stlsort, quicksort, quickinssort, mergesort,
  1358. mergeinssort, shellsort, shellsortsedgwick, radixsort, radixsortmsd, timsort,
  1359. myshell1, myshell2, myshell3, bucketquicksort, bucketquickinssort };
  1360. string names3[18] =
  1361. { "combsort", "bucketinssort", "heapsort", "stlsort", "quicksort", "quickinssort",
  1362. "mergesort", "mergeinssort", "shellsort", "shellsortsedgwick", "radixsort",
  1363. "radixsortmsd", "timsort", "myshell1", "myshell2", "myshell3",
  1364. "bucketquicksort", "bucketquickinssort" };*/
  1365.  
  1366. const int N = 100000000;
  1367. int arr[N];
  1368.  
  1369. void testprint(int n, string section) {
  1370.     string s = section + "\\test" + to_string(curt) + ".txt";
  1371.     freopen(s.c_str(), "w", stdout);
  1372.     printf("%d\n", n);
  1373.     for (int i = 0; i < n; i++)
  1374.         printf("%d ", arr[i]);
  1375.     fclose(stdout);
  1376.     curt++;
  1377. }
  1378. void testprint(vector<int> &a, string section) {
  1379.     string s = section + "\\test" + to_string(curt) + ".txt";
  1380.     freopen(s.c_str(), "w", stdout);
  1381.     int n = a.size();
  1382.     printf("%d\n", n);
  1383.     for (int i = 0; i < n; i++)
  1384.         printf("%d ", a[i]);
  1385.     fclose(stdout);
  1386.     curt++;
  1387. }
  1388.  
  1389. void testgen1() {
  1390.     string section = "Random";
  1391.     vector<int> arr;
  1392.     for (int q = 0; q < 4; q++) {
  1393.         int n = len[q];
  1394.         if (arr.size() != n) arr.resize(n);
  1395.         for (int w = 0; w < 5; w++) {
  1396.             for (int j = 0; j < n; j++)
  1397.                 arr[j] = randint() % (int)10;
  1398.             testprint(arr, section);
  1399.         }
  1400.         for (int w = 0; w < 5; w++) {
  1401.             for (int j = 0; j < n; j++)
  1402.                 arr[j] = randint() % (int)1000;
  1403.             testprint(arr, section);
  1404.         }
  1405.         for (int w = 0; w < 5; w++) {
  1406.             for (int j = 0; j < n; j++)
  1407.                 arr[j] = randint() % (int)1e5;
  1408.             testprint(arr, section);
  1409.         }
  1410.         for (int w = 0; w < 5; w++) {
  1411.             for (int j = 0; j < n; j++)
  1412.                 arr[j] = randint() % (int)1e7;
  1413.             testprint(arr, section);
  1414.         }
  1415.         for (int w = 0; w < 10; w++) {
  1416.             for (int j = 0; j < n; j++)
  1417.                 arr[j] = randint() % (int)1e9;
  1418.             testprint(arr, section);
  1419.         }
  1420.     }
  1421. }
  1422. void testgen2() {
  1423.     string section = "Part sorted";
  1424.     vector<int> arr;
  1425.     for (int q = 0; q < 4; q++) {
  1426.         int n = len[q];
  1427.         if (arr.size() != n) arr.resize(n);
  1428.         for (int w = 0; w < 5; w++) {
  1429.             for (int j = 0; j < n; j++)
  1430.                 arr[j] = randint() % (int)1e9;
  1431.             int cur = 0;
  1432.             while (cur < n) {
  1433.                 int l = randint() % min((int)10, n - cur) + 1;
  1434.                 sort(arr.begin() + cur, arr.begin() + cur + l);
  1435.                 cur += l;
  1436.             }
  1437.             testprint(arr, section);
  1438.         }
  1439.         for (int w = 0; w < 5; w++) {
  1440.             for (int j = 0; j < n; j++)
  1441.                 arr[j] = randint() % (int)1e9;
  1442.             int cur = 0;
  1443.             while (cur < n) {
  1444.                 int l = randint() % min((int)100, n - cur) + 1;
  1445.                 sort(arr.begin() + cur, arr.begin() + cur + l);
  1446.                 cur += l;
  1447.             }
  1448.             testprint(arr, section);
  1449.         }
  1450.         for (int w = 0; w < 5; w++) {
  1451.             for (int j = 0; j < n; j++)
  1452.                 arr[j] = randint() % (int)1e9;
  1453.             int cur = 0;
  1454.             while (cur < n) {
  1455.                 int l = randint() % min((int)1000, n - cur) + 1;
  1456.                 sort(arr.begin() + cur, arr.begin() + cur + l);
  1457.                 cur += l;
  1458.             }
  1459.             testprint(arr, section);
  1460.         }
  1461.         for (int w = 0; w < 5; w++) {
  1462.             for (int j = 0; j < n; j++)
  1463.                 arr[j] = randint() % (int)1e9;
  1464.             int cur = 0;
  1465.             while (cur < n) {
  1466.                 int l = randint() % min((int)1e4, n - cur) + 1;
  1467.                 sort(arr.begin() + cur, arr.begin() + cur + l);
  1468.                 cur += l;
  1469.             }
  1470.             testprint(arr, section);
  1471.         }
  1472.         for (int w = 0; w < 5; w++) {
  1473.             for (int j = 0; j < n; j++)
  1474.                 arr[j] = randint() % (int)1e9;
  1475.             int cur = 0;
  1476.             while (cur < n) {
  1477.                 int l = randint() % min((int)1e5, n - cur) + 1;
  1478.                 sort(arr.begin() + cur, arr.begin() + cur + l);
  1479.                 cur += l;
  1480.             }
  1481.             testprint(arr, section);
  1482.         }
  1483.         if (n == 1e5) continue;
  1484.         for (int w = 0; w < 5; w++) {
  1485.             for (int j = 0; j < n; j++)
  1486.                 arr[j] = randint() % (int)1e9;
  1487.             int cur = 0;
  1488.             while (cur < n) {
  1489.                 int l = randint() % min((int)1e6, n - cur) + 1;
  1490.                 sort(arr.begin() + cur, arr.begin() + cur + l);
  1491.                 cur += l;
  1492.             }
  1493.             testprint(arr, section);
  1494.         }
  1495.         if (n == 1e6) continue;
  1496.         for (int w = 0; w < 5; w++) {
  1497.             for (int j = 0; j < n; j++)
  1498.                 arr[j] = randint() % (int)1e9;
  1499.             int cur = 0;
  1500.             while (cur < n) {
  1501.                 int l = randint() % min((int)1e7, n - cur) + 1;
  1502.                 sort(arr.begin() + cur, arr.begin() + cur + l);
  1503.                 cur += l;
  1504.             }
  1505.             testprint(arr, section);
  1506.         }
  1507.         if (n == 1e7) continue;
  1508.         for (int w = 0; w < 5; w++) {
  1509.             for (int j = 0; j < n; j++)
  1510.                 arr[j] = randint() % (int)1e9;
  1511.             int cur = 0;
  1512.             while (cur < n) {
  1513.                 int l = randint() % min((int)1e8, n - cur) + 1;
  1514.                 sort(arr.begin() + cur, arr.begin() + cur + l);
  1515.                 cur += l;
  1516.             }
  1517.             testprint(arr, section);
  1518.         }
  1519.     }
  1520. }
  1521. void testgen3() {
  1522.     string section = "Swaps";
  1523.     vector<int> arr;
  1524.     for (int q = 0; q < 4; q++) {
  1525.         int n = len[q];
  1526.         if (arr.size() != n) arr.resize(n);
  1527.         for (int w = 0; w < 5; w++) {
  1528.             for (int j = 0; j < n; j++)
  1529.                 arr[j] = randint() % (int)1e9;
  1530.             radixsort(arr);
  1531.             for (int d = 0; d < 10; d++) {
  1532.                 int p1 = 1, p2 = 1;
  1533.                 while (p1 == p2) {
  1534.                     p1 = randint() % n;
  1535.                     p2 = randint() % n;
  1536.                 }
  1537.                 swap(arr[p1], arr[p2]);
  1538.             }
  1539.             testprint(arr, section);
  1540.         }
  1541.         for (int w = 0; w < 5; w++) {
  1542.             for (int j = 0; j < n; j++)
  1543.                 arr[j] = randint() % (int)1e9;
  1544.             radixsort(arr);
  1545.             for (int d = 0; d < 100; d++) {
  1546.                 int p1 = 1, p2 = 1;
  1547.                 while (p1 == p2) {
  1548.                     p1 = randint() % n;
  1549.                     p2 = randint() % n;
  1550.                 }
  1551.                 swap(arr[p1], arr[p2]);
  1552.             }
  1553.             testprint(arr, section);
  1554.         }
  1555.         for (int w = 0; w < 5; w++) {
  1556.             for (int j = 0; j < n; j++)
  1557.                 arr[j] = randint() % (int)1e9;
  1558.             radixsort(arr);
  1559.             for (int d = 0; d < 1000; d++) {
  1560.                 int p1 = 1, p2 = 1;
  1561.                 while (p1 == p2) {
  1562.                     p1 = randint() % n;
  1563.                     p2 = randint() % n;
  1564.                 }
  1565.                 swap(arr[p1], arr[p2]);
  1566.             }
  1567.             testprint(arr, section);
  1568.         }
  1569.         for (int w = 0; w < 5; w++) {
  1570.             for (int j = 0; j < n; j++)
  1571.                 arr[j] = randint() % (int)1e9;
  1572.             radixsort(arr);
  1573.             for (int d = 0; d < 10000; d++) {
  1574.                 int p1 = 1, p2 = 1;
  1575.                 while (p1 == p2) {
  1576.                     p1 = randint() % n;
  1577.                     p2 = randint() % n;
  1578.                 }
  1579.                 swap(arr[p1], arr[p2]);
  1580.             }
  1581.             testprint(arr, section);
  1582.         }
  1583.         for (int w = 0; w < 5; w++) {
  1584.             for (int j = 0; j < n; j++)
  1585.                 arr[j] = randint() % (int)1e9;
  1586.             radixsort(arr);
  1587.             for (int d = 0; d < 1e5; d++) {
  1588.                 int p1 = 1, p2 = 1;
  1589.                 while (p1 == p2) {
  1590.                     p1 = randint() % n;
  1591.                     p2 = randint() % n;
  1592.                 }
  1593.                 swap(arr[p1], arr[p2]);
  1594.             }
  1595.             testprint(arr, section);
  1596.         }
  1597.         if (n == 1e5) continue;
  1598.         for (int w = 0; w < 5; w++) {
  1599.             for (int j = 0; j < n; j++)
  1600.                 arr[j] = randint() % (int)1e9;
  1601.             radixsort(arr);
  1602.             for (int d = 0; d < 1e6; d++) {
  1603.                 int p1 = 1, p2 = 1;
  1604.                 while (p1 == p2) {
  1605.                     p1 = randint() % n;
  1606.                     p2 = randint() % n;
  1607.                 }
  1608.                 swap(arr[p1], arr[p2]);
  1609.             }
  1610.             testprint(arr, section);
  1611.         }
  1612.         if (n == 1e6) continue;
  1613.         for (int w = 0; w < 5; w++) {
  1614.             for (int j = 0; j < n; j++)
  1615.                 arr[j] = randint() % (int)1e9;
  1616.             radixsort(arr);
  1617.             for (int d = 0; d < 1e7; d++) {
  1618.                 int p1 = 1, p2 = 1;
  1619.                 while (p1 == p2) {
  1620.                     p1 = randint() % n;
  1621.                     p2 = randint() % n;
  1622.                 }
  1623.                 swap(arr[p1], arr[p2]);
  1624.             }
  1625.             testprint(arr, section);
  1626.         }
  1627.         if (n == 1e7) continue;
  1628.         for (int w = 0; w < 5; w++) {
  1629.             for (int j = 0; j < n; j++)
  1630.                 arr[j] = randint() % (int)1e9;
  1631.             radixsort(arr);
  1632.             for (int d = 0; d < 1e8; d++) {
  1633.                 int p1 = 1, p2 = 1;
  1634.                 while (p1 == p2) {
  1635.                     p1 = randint() % n;
  1636.                     p2 = randint() % n;
  1637.                 }
  1638.                 swap(arr[p1], arr[p2]);
  1639.             }
  1640.             testprint(arr, section);
  1641.         }
  1642.     }
  1643. }
  1644. void testgen4() {
  1645.     string section = "Additional";
  1646.     for (int q = 0; q < 4; q++) {
  1647.         int n = len[q];
  1648.         for (int i = 0; i < n; i++)
  1649.             arr[i] = i + 1;
  1650.         testprint(n, section);
  1651.         for (int i = 0; i < n; i++)
  1652.             arr[i] = n - i;
  1653.         testprint(n, section);
  1654.         for (int w = 0; w < 2; w++) {
  1655.             for (int i = 0; i < n; i++)
  1656.                 arr[i] = randint() % (int)1e9;
  1657.             radixsort(arr, arr + n);
  1658.             testprint(n, section);
  1659.         }
  1660.         for (int w = 0; w < 2; w++) {
  1661.             for (int i = 0; i < n; i++)
  1662.                 arr[i] = randint() % (int)1e9;
  1663.             radixsort(arr, arr + n);
  1664.             reverse(arr, arr + n);
  1665.             testprint(n, section);
  1666.         }
  1667.         for (int w = 0; w < 2; w++) {
  1668.             for (int i = 0; i < n; i++)
  1669.                 arr[i] = i + 1;
  1670.             for (int i = 0; i < 10; i++) {
  1671.                 int pos = randint() % n;
  1672.                 int v = randint() % (int)1e9;
  1673.                 arr[pos] = v;
  1674.             }
  1675.             testprint(n, section);
  1676.         }
  1677.         for (int w = 0; w < 2; w++) {
  1678.             for (int i = 0; i < n; i++)
  1679.                 arr[i] = i + 1;
  1680.             for (int i = 0; i < 100; i++) {
  1681.                 int pos = randint() % n;
  1682.                 int v = randint() % (int)1e9;
  1683.                 arr[pos] = v;
  1684.             }
  1685.             testprint(n, section);
  1686.         }
  1687.         for (int w = 0; w < 2; w++) {
  1688.             for (int i = 0; i < n; i++)
  1689.                 arr[i] = i + 1;
  1690.             for (int i = 0; i < 1000; i++) {
  1691.                 int pos = randint() % n;
  1692.                 int v = randint() % (int)1e9;
  1693.                 arr[pos] = v;
  1694.             }
  1695.             testprint(n, section);
  1696.         }
  1697.         for (int w = 0; w < 2; w++) {
  1698.             for (int i = 0; i < n; i++)
  1699.                 arr[i] = i + 1;
  1700.             for (int i = 0; i < 1e4; i++) {
  1701.                 int pos = randint() % n;
  1702.                 int v = randint() % (int)1e9;
  1703.                 arr[pos] = v;
  1704.             }
  1705.             testprint(n, section);
  1706.         }
  1707.         for (int w = 0; w < 2; w++) {
  1708.             for (int i = 0; i < n; i++)
  1709.                 arr[i] = i + 1;
  1710.             for (int i = 0; i < 1e5; i++) {
  1711.                 int pos = randint() % n;
  1712.                 int v = randint() % (int)1e9;
  1713.                 arr[pos] = v;
  1714.             }
  1715.             testprint(n, section);
  1716.         }
  1717.         if (n > 1e5) {
  1718.             for (int w = 0; w < 2; w++) {
  1719.                 for (int i = 0; i < n; i++)
  1720.                     arr[i] = i + 1;
  1721.                 for (int i = 0; i < 1e6; i++) {
  1722.                     int pos = randint() % n;
  1723.                     int v = randint() % (int)1e9;
  1724.                     arr[pos] = v;
  1725.                 }
  1726.                 testprint(n, section);
  1727.             }
  1728.             if (n > 1e6) {
  1729.                 for (int w = 0; w < 2; w++) {
  1730.                     for (int i = 0; i < n; i++)
  1731.                         arr[i] = i + 1;
  1732.                     for (int i = 0; i < 1e7; i++) {
  1733.                         int pos = randint() % n;
  1734.                         int v = randint() % (int)1e9;
  1735.                         arr[pos] = v;
  1736.                     }
  1737.                     testprint(n, section);
  1738.                 }
  1739.                 if (n > 1e7) {
  1740.                     for (int w = 0; w < 2; w++) {
  1741.                         for (int i = 0; i < n; i++)
  1742.                             arr[i] = i + 1;
  1743.                         for (int i = 0; i < 1e8; i++) {
  1744.                             int pos = randint() % n;
  1745.                             int v = randint() % (int)1e9;
  1746.                             arr[pos] = v;
  1747.                         }
  1748.                         testprint(n, section);
  1749.                     }
  1750.                 }
  1751.             }
  1752.         }
  1753.         for (int w = 0; w < 3; w++) {
  1754.             int repeat = randint() % (int)1e9;
  1755.             int nn = n / 10;
  1756.             for (int i = 0; i < nn; i++)
  1757.                 arr[i] = repeat;
  1758.             for (int i = nn; i < n; i++)
  1759.                 arr[i] = randint() % (int)1e9;
  1760.             random_shuffle(arr, arr + n);
  1761.             testprint(n, section);
  1762.         }
  1763.         for (int w = 0; w < 3; w++) {
  1764.             int repeat = randint() % (int)1e9;
  1765.             int nn = n / 4;
  1766.             for (int i = 0; i < nn; i++)
  1767.                 arr[i] = repeat;
  1768.             for (int i = nn; i < n; i++)
  1769.                 arr[i] = randint() % (int)1e9;
  1770.             random_shuffle(arr, arr + n);
  1771.             testprint(n, section);
  1772.         }
  1773.         for (int w = 0; w < 3; w++) {
  1774.             int repeat = randint() % (int)1e9;
  1775.             int nn = n / 2;
  1776.             for (int i = 0; i < nn; i++)
  1777.                 arr[i] = repeat;
  1778.             for (int i = nn; i < n; i++)
  1779.                 arr[i] = randint() % (int)1e9;
  1780.             random_shuffle(arr, arr + n);
  1781.             testprint(n, section);
  1782.         }
  1783.         for (int w = 0; w < 3; w++) {
  1784.             int repeat = randint() % (int)1e9;
  1785.             int nn = 3 * n / 4;
  1786.             for (int i = 0; i < nn; i++)
  1787.                 arr[i] = repeat;
  1788.             for (int i = nn; i < n; i++)
  1789.                 arr[i] = randint() % (int)1e9;
  1790.             random_shuffle(arr, arr + n);
  1791.             testprint(n, section);
  1792.         }
  1793.         for (int w = 0; w < 3; w++) {
  1794.             int repeat = randint() % (int)1e9;
  1795.             int nn = 9 * n / 10;
  1796.             for (int i = 0; i < nn; i++)
  1797.                 arr[i] = repeat;
  1798.             for (int i = nn; i < n; i++)
  1799.                 arr[i] = randint() % (int)1e9;
  1800.             random_shuffle(arr, arr + n);
  1801.             testprint(n, section);
  1802.         }
  1803.     }
  1804. }
  1805. int cur[N];
  1806. int ans[N];
  1807. int made[N];
  1808. int read(string &test) {
  1809.     freopen(test.c_str(), "r", stdin);
  1810.     int n;
  1811.     scanf("%d", &n);
  1812.     for (int i = 0; i < n; i++)
  1813.         scanf("%d", &cur[i]);
  1814.     for (int i = 0; i < n; i++)
  1815.         ans[i] = cur[i];
  1816.     fclose(stdin);
  1817.     radixsort(ans, ans + n);
  1818.     return n;
  1819. }
  1820. bool check(int n) {
  1821.     bool right = true;
  1822.     for (int i = 0; i < n; i++)
  1823.         if (ans[i] != made[i])
  1824.             right = false;
  1825.     return right;
  1826. }
  1827. bool fasttest(string section, int num) {
  1828.     string s = section + "\\test" + to_string(num) + ".txt";
  1829.     freopen(s.c_str(), "r", stdin);
  1830.     int n;
  1831.     scanf("%d", &n);
  1832.     for (int i = 0; i < n; i++)
  1833.         scanf("%d", &cur[i]);
  1834.     for (int i = 0; i < n; i++)
  1835.         ans[i] = cur[i];
  1836.     radixsort(ans, ans + n);
  1837.     int t1, t2;
  1838.     for (int run = 0; run < 20; run++) {
  1839.         for (int i = 0; i < n; i++)
  1840.             made[i] = cur[i];
  1841.         t1 = clock();
  1842.         mergesort(made, made + n);
  1843.         t2 = clock();
  1844.         if (check(n)) cout << t2 - t1 << " ";
  1845.         else {
  1846.             cout << "incorrect";
  1847.             return false;
  1848.         }
  1849.     }
  1850.     return true;
  1851. }
  1852. void fasttestpart() {
  1853.     string output;
  1854.     output = "Results\\shellsorthibr1e6.txt";
  1855.     freopen(output.c_str(), "w", stdout);
  1856.     for (int t = 31; t <= 60; t++) {
  1857.         int n = read("Random\\test" + to_string(t) + ".txt");
  1858.         for (int run = 1; run <= 20; run++) {
  1859.             for (int i = 0; i < n; i++)
  1860.                 made[i] = cur[i];
  1861.             int t1 = clock();
  1862.             shellsorthib(made, made + n);
  1863.             int t2 = clock();
  1864.             if (!check(n)) printf("incorrect");
  1865.             else printf("%d", t2 - t1);
  1866.             if (run != 20) printf(" ");
  1867.             else printf("\n");
  1868.         }
  1869.     }
  1870.     fclose(stdout);
  1871.     output = "Results\\shellsorthibr1e7.txt";
  1872.     freopen(output.c_str(), "w", stdout);
  1873.     for (int t = 61; t <= 90; t++) {
  1874.         int n = read("Random\\test" + to_string(t) + ".txt");
  1875.         for (int run = 1; run <= 20; run++) {
  1876.             for (int i = 0; i < n; i++)
  1877.                 made[i] = cur[i];
  1878.             int t1 = clock();
  1879.             shellsorthib(made, made + n);
  1880.             int t2 = clock();
  1881.             if (!check(n)) printf("incorrect");
  1882.             else printf("%d", t2 - t1);
  1883.             if (run != 20) printf(" ");
  1884.             else printf("\n");
  1885.         }
  1886.     }
  1887.     fclose(stdout);
  1888.     output = "Results\\shellsorthibp1e6.txt";
  1889.     freopen(output.c_str(), "w", stdout);
  1890.     for (int t = 26; t <= 55; t++) {
  1891.         int n = read("Part sorted\\test" + to_string(t) + ".txt");
  1892.         for (int run = 1; run <= 20; run++) {
  1893.             for (int i = 0; i < n; i++)
  1894.                 made[i] = cur[i];
  1895.             int t1 = clock();
  1896.             shellsorthib(made, made + n);
  1897.             int t2 = clock();
  1898.             if (!check(n)) printf("incorrect");
  1899.             else printf("%d", t2 - t1);
  1900.             if (run != 20) printf(" ");
  1901.             else printf("\n");
  1902.         }
  1903.     }
  1904.     fclose(stdout);
  1905.     output = "Results\\shellsorthibp1e7.txt";
  1906.     freopen(output.c_str(), "w", stdout);
  1907.     for (int t = 56; t <= 90; t++) {
  1908.         int n = read("Part sorted\\test" + to_string(t) + ".txt");
  1909.         for (int run = 1; run <= 20; run++) {
  1910.             for (int i = 0; i < n; i++)
  1911.                 made[i] = cur[i];
  1912.             int t1 = clock();
  1913.             shellsorthib(made, made + n);
  1914.             int t2 = clock();
  1915.             if (!check(n)) printf("incorrect");
  1916.             else printf("%d", t2 - t1);
  1917.             if (run != 20) printf(" ");
  1918.             else printf("\n");
  1919.         }
  1920.     }
  1921.     fclose(stdout);
  1922.     output = "Results\\shellsorthibs1e6.txt";
  1923.     freopen(output.c_str(), "w", stdout);
  1924.     for (int t = 26; t <= 55; t++) {
  1925.         int n = read("Swaps\\test" + to_string(t) + ".txt");
  1926.         for (int run = 1; run <= 20; run++) {
  1927.             for (int i = 0; i < n; i++)
  1928.                 made[i] = cur[i];
  1929.             int t1 = clock();
  1930.             shellsorthib(made, made + n);
  1931.             int t2 = clock();
  1932.             if (!check(n)) printf("incorrect");
  1933.             else printf("%d", t2 - t1);
  1934.             if (run != 20) printf(" ");
  1935.             else printf("\n");
  1936.         }
  1937.     }
  1938.     fclose(stdout);
  1939.     output = "Results\\shellsorthibs1e7.txt";
  1940.     freopen(output.c_str(), "w", stdout);
  1941.     for (int t = 56; t <= 90; t++) {
  1942.         int n = read("Swaps\\test" + to_string(t) + ".txt");
  1943.         for (int run = 1; run <= 20; run++) {
  1944.             for (int i = 0; i < n; i++)
  1945.                 made[i] = cur[i];
  1946.             int t1 = clock();
  1947.             shellsorthib(made, made + n);
  1948.             int t2 = clock();
  1949.             if (!check(n)) printf("incorrect");
  1950.             else printf("%d", t2 - t1);
  1951.             if (run != 20) printf(" ");
  1952.             else printf("\n");
  1953.         }
  1954.     }
  1955.     fclose(stdout);
  1956.     output = "Results\\shellsorthiba1e6.txt";
  1957.     freopen(output.c_str(), "w", stdout);
  1958.     for (int t = 32; t <= 64; t++) {
  1959.         int n = read("Additional\\test" + to_string(t) + ".txt");
  1960.         for (int run = 1; run <= 20; run++) {
  1961.             for (int i = 0; i < n; i++)
  1962.                 made[i] = cur[i];
  1963.             int t1 = clock();
  1964.             shellsorthib(made, made + n);
  1965.             int t2 = clock();
  1966.             if (!check(n)) printf("incorrect");
  1967.             else printf("%d", t2 - t1);
  1968.             if (run != 20) printf(" ");
  1969.             else printf("\n");
  1970.         }
  1971.     }
  1972.     fclose(stdout);
  1973.     output = "Results\\shellsorthiba1e7.txt";
  1974.     freopen(output.c_str(), "w", stdout);
  1975.     for (int t = 65; t <= 99; t++) {
  1976.         int n = read("Additional\\test" + to_string(t) + ".txt");
  1977.         for (int run = 1; run <= 20; run++) {
  1978.             for (int i = 0; i < n; i++)
  1979.                 made[i] = cur[i];
  1980.             int t1 = clock();
  1981.             shellsorthib(made, made + n);
  1982.             int t2 = clock();
  1983.             if (!check(n)) printf("incorrect");
  1984.             else printf("%d", t2 - t1);
  1985.             if (run != 20) printf(" ");
  1986.             else printf("\n");
  1987.         }
  1988.     }
  1989.     fclose(stdout);
  1990. }
  1991. void exttest() {
  1992.     string output;
  1993.     output = "Results\\Random\\combsort1e7.txt";
  1994.     freopen(output.c_str(), "w", stdout);
  1995.     for (int t = 61; t <= 90; t++) {
  1996.         int n = read("Random\\test" + to_string(t) + ".txt");
  1997.         for (int run = 1; run <= 20; run++) {
  1998.             for (int i = 0; i < n; i++)
  1999.                 made[i] = cur[i];
  2000.             int t1 = clock();
  2001.             combsort(made, made + n);
  2002.             int t2 = clock();
  2003.             if (!check(n)) printf("incorrect");
  2004.             else printf("%d", t2 - t1);
  2005.             if (run != 20) printf(" ");
  2006.             else printf("\n");
  2007.         }
  2008.     }
  2009.     fclose(stdout);
  2010.     output = "Results\\Random\\quicksort1e7.txt";
  2011.     freopen(output.c_str(), "w", stdout);
  2012.     for (int t = 61; t <= 90; t++) {
  2013.         int n = read("Random\\test" + to_string(t) + ".txt");
  2014.         for (int run = 1; run <= 20; run++) {
  2015.             for (int i = 0; i < n; i++)
  2016.                 made[i] = cur[i];
  2017.             int t1 = clock();
  2018.             quicksort(made, made + n);
  2019.             int t2 = clock();
  2020.             if (!check(n)) printf("incorrect");
  2021.             else printf("%d", t2 - t1);
  2022.             if (run != 20) printf(" ");
  2023.             else printf("\n");
  2024.         }
  2025.     }
  2026.     fclose(stdout);
  2027.     output = "Results\\Random\\quickinssort1e7.txt";
  2028.     freopen(output.c_str(), "w", stdout);
  2029.     for (int t = 61; t <= 90; t++) {
  2030.         int n = read("Random\\test" + to_string(t) + ".txt");
  2031.         for (int run = 1; run <= 20; run++) {
  2032.             for (int i = 0; i < n; i++)
  2033.                 made[i] = cur[i];
  2034.             int t1 = clock();
  2035.             quickinssort(made, made + n);
  2036.             int t2 = clock();
  2037.             if (!check(n)) printf("incorrect");
  2038.             else printf("%d", t2 - t1);
  2039.             if (run != 20) printf(" ");
  2040.             else printf("\n");
  2041.         }
  2042.     }
  2043.     fclose(stdout);
  2044.     output = "Results\\Random\\mergeinssort1e7.txt";
  2045.     freopen(output.c_str(), "w", stdout);
  2046.     for (int t = 61; t <= 90; t++) {
  2047.         int n = read("Random\\test" + to_string(t) + ".txt");
  2048.         for (int run = 1; run <= 20; run++) {
  2049.             for (int i = 0; i < n; i++)
  2050.                 made[i] = cur[i];
  2051.             int t1 = clock();
  2052.             mergeinssort(made, made + n);
  2053.             int t2 = clock();
  2054.             if (!check(n)) printf("incorrect");
  2055.             else printf("%d", t2 - t1);
  2056.             if (run != 20) printf(" ");
  2057.             else printf("\n");
  2058.         }
  2059.     }
  2060.     fclose(stdout);
  2061.     output = "Results\\Random\\radixsortmsd1e7.txt";
  2062.     freopen(output.c_str(), "w", stdout);
  2063.     for (int t = 61; t <= 90; t++) {
  2064.         int n = read("Random\\test" + to_string(t) + ".txt");
  2065.         for (int run = 1; run <= 20; run++) {
  2066.             for (int i = 0; i < n; i++)
  2067.                 made[i] = cur[i];
  2068.             int t1 = clock();
  2069.             radixsortmsd(made, made + n);
  2070.             int t2 = clock();
  2071.             if (!check(n)) printf("incorrect");
  2072.             else printf("%d", t2 - t1);
  2073.             if (run != 20) printf(" ");
  2074.             else printf("\n");
  2075.         }
  2076.     }
  2077.     fclose(stdout);
  2078.     output = "Results\\Random\\quicksort1e8.txt";
  2079.     freopen(output.c_str(), "w", stdout);
  2080.     for (int t = 91; t <= 120; t++) {
  2081.         int n = read("Random\\test" + to_string(t) + ".txt");
  2082.         for (int run = 1; run <= 20; run++) {
  2083.             for (int i = 0; i < n; i++)
  2084.                 made[i] = cur[i];
  2085.             int t1 = clock();
  2086.             quicksort(made, made + n);
  2087.             int t2 = clock();
  2088.             if (!check(n)) printf("incorrect");
  2089.             else printf("%d", t2 - t1);
  2090.             if (run != 20) printf(" ");
  2091.             else printf("\n");
  2092.         }
  2093.     }
  2094.     fclose(stdout);
  2095.     output = "Results\\Random\\quickinssort1e8.txt";
  2096.     freopen(output.c_str(), "w", stdout);
  2097.     for (int t = 91; t <= 120; t++) {
  2098.         int n = read("Random\\test" + to_string(t) + ".txt");
  2099.         for (int run = 1; run <= 20; run++) {
  2100.             for (int i = 0; i < n; i++)
  2101.                 made[i] = cur[i];
  2102.             int t1 = clock();
  2103.             quickinssort(made, made + n);
  2104.             int t2 = clock();
  2105.             if (!check(n)) printf("incorrect");
  2106.             else printf("%d", t2 - t1);
  2107.             if (run != 20) printf(" ");
  2108.             else printf("\n");
  2109.         }
  2110.     }
  2111.     fclose(stdout);
  2112.     output = "Results\\Random\\mergeinssort1e8.txt";
  2113.     freopen(output.c_str(), "w", stdout);
  2114.     for (int t = 91; t <= 120; t++) {
  2115.         int n = read("Random\\test" + to_string(t) + ".txt");
  2116.         for (int run = 1; run <= 20; run++) {
  2117.             for (int i = 0; i < n; i++)
  2118.                 made[i] = cur[i];
  2119.             int t1 = clock();
  2120.             mergeinssort(made, made + n);
  2121.             int t2 = clock();
  2122.             if (!check(n)) printf("incorrect");
  2123.             else printf("%d", t2 - t1);
  2124.             if (run != 20) printf(" ");
  2125.             else printf("\n");
  2126.         }
  2127.     }
  2128.     fclose(stdout);
  2129.     output = "Results\\Random\\radixsortmsd1e8.txt";
  2130.     freopen(output.c_str(), "w", stdout);
  2131.     for (int t = 91; t <= 120; t++) {
  2132.         int n = read("Random\\test" + to_string(t) + ".txt");
  2133.         for (int run = 1; run <= 20; run++) {
  2134.             for (int i = 0; i < n; i++)
  2135.                 made[i] = cur[i];
  2136.             int t1 = clock();
  2137.             radixsortmsd(made, made + n);
  2138.             int t2 = clock();
  2139.             if (!check(n)) printf("incorrect");
  2140.             else printf("%d", t2 - t1);
  2141.             if (run != 20) printf(" ");
  2142.             else printf("\n");
  2143.         }
  2144.     }
  2145.     fclose(stdout);
  2146.     output = "Results\\Part sorted\\quicksort1e7.txt";
  2147.     freopen(output.c_str(), "w", stdout);
  2148.     for (int t = 56; t <= 90; t++) {
  2149.         int n = read("Part sorted\\test" + to_string(t) + ".txt");
  2150.         for (int run = 1; run <= 20; run++) {
  2151.             for (int i = 0; i < n; i++)
  2152.                 made[i] = cur[i];
  2153.             int t1 = clock();
  2154.             quicksort(made, made + n);
  2155.             int t2 = clock();
  2156.             if (!check(n)) printf("incorrect");
  2157.             else printf("%d", t2 - t1);
  2158.             if (run != 20) printf(" ");
  2159.             else printf("\n");
  2160.         }
  2161.     }
  2162.     fclose(stdout);
  2163.     output = "Results\\Part sorted\\quickinssort1e7.txt";
  2164.     freopen(output.c_str(), "w", stdout);
  2165.     for (int t = 56; t <= 90; t++) {
  2166.         int n = read("Part sorted\\test" + to_string(t) + ".txt");
  2167.         for (int run = 1; run <= 20; run++) {
  2168.             for (int i = 0; i < n; i++)
  2169.                 made[i] = cur[i];
  2170.             int t1 = clock();
  2171.             quickinssort(made, made + n);
  2172.             int t2 = clock();
  2173.             if (!check(n)) printf("incorrect");
  2174.             else printf("%d", t2 - t1);
  2175.             if (run != 20) printf(" ");
  2176.             else printf("\n");
  2177.         }
  2178.     }
  2179.     fclose(stdout);
  2180.     output = "Results\\Part sorted\\mergeinssort1e7.txt";
  2181.     freopen(output.c_str(), "w", stdout);
  2182.     for (int t = 56; t <= 90; t++) {
  2183.         int n = read("Part sorted\\test" + to_string(t) + ".txt");
  2184.         for (int run = 1; run <= 20; run++) {
  2185.             for (int i = 0; i < n; i++)
  2186.                 made[i] = cur[i];
  2187.             int t1 = clock();
  2188.             mergeinssort(made, made + n);
  2189.             int t2 = clock();
  2190.             if (!check(n)) printf("incorrect");
  2191.             else printf("%d", t2 - t1);
  2192.             if (run != 20) printf(" ");
  2193.             else printf("\n");
  2194.         }
  2195.     }
  2196.     fclose(stdout);
  2197.     output = "Results\\Part sorted\\radixsortmsd1e7.txt";
  2198.     freopen(output.c_str(), "w", stdout);
  2199.     for (int t = 56; t <= 90; t++) {
  2200.         int n = read("Part sorted\\test" + to_string(t) + ".txt");
  2201.         for (int run = 1; run <= 20; run++) {
  2202.             for (int i = 0; i < n; i++)
  2203.                 made[i] = cur[i];
  2204.             int t1 = clock();
  2205.             radixsortmsd(made, made + n);
  2206.             int t2 = clock();
  2207.             if (!check(n)) printf("incorrect");
  2208.             else printf("%d", t2 - t1);
  2209.             if (run != 20) printf(" ");
  2210.             else printf("\n");
  2211.         }
  2212.     }
  2213.     fclose(stdout);
  2214.     output = "Results\\Part sorted\\quicksort1e8.txt";
  2215.     freopen(output.c_str(), "w", stdout);
  2216.     for (int t = 91; t <= 130; t++) {
  2217.         int n = read("Part sorted\\test" + to_string(t) + ".txt");
  2218.         for (int run = 1; run <= 20; run++) {
  2219.             for (int i = 0; i < n; i++)
  2220.                 made[i] = cur[i];
  2221.             int t1 = clock();
  2222.             quicksort(made, made + n);
  2223.             int t2 = clock();
  2224.             if (!check(n)) printf("incorrect");
  2225.             else printf("%d", t2 - t1);
  2226.             if (run != 20) printf(" ");
  2227.             else printf("\n");
  2228.         }
  2229.     }
  2230.     fclose(stdout);
  2231.     output = "Results\\Part sorted\\quickinssort1e8.txt";
  2232.     freopen(output.c_str(), "w", stdout);
  2233.     for (int t = 91; t <= 130; t++) {
  2234.         int n = read("Part sorted\\test" + to_string(t) + ".txt");
  2235.         for (int run = 1; run <= 20; run++) {
  2236.             for (int i = 0; i < n; i++)
  2237.                 made[i] = cur[i];
  2238.             int t1 = clock();
  2239.             quickinssort(made, made + n);
  2240.             int t2 = clock();
  2241.             if (!check(n)) printf("incorrect");
  2242.             else printf("%d", t2 - t1);
  2243.             if (run != 20) printf(" ");
  2244.             else printf("\n");
  2245.         }
  2246.     }
  2247.     fclose(stdout);
  2248.     output = "Results\\Part sorted\\mergeinssort1e8.txt";
  2249.     freopen(output.c_str(), "w", stdout);
  2250.     for (int t = 91; t <= 130; t++) {
  2251.         int n = read("Part sorted\\test" + to_string(t) + ".txt");
  2252.         for (int run = 1; run <= 20; run++) {
  2253.             for (int i = 0; i < n; i++)
  2254.                 made[i] = cur[i];
  2255.             int t1 = clock();
  2256.             mergeinssort(made, made + n);
  2257.             int t2 = clock();
  2258.             if (!check(n)) printf("incorrect");
  2259.             else printf("%d", t2 - t1);
  2260.             if (run != 20) printf(" ");
  2261.             else printf("\n");
  2262.         }
  2263.     }
  2264.     fclose(stdout);
  2265.     output = "Results\\Part sorted\\radixsortmsd1e8.txt";
  2266.     freopen(output.c_str(), "w", stdout);
  2267.     for (int t = 91; t <= 130; t++) {
  2268.         int n = read("Part sorted\\test" + to_string(t) + ".txt");
  2269.         for (int run = 1; run <= 20; run++) {
  2270.             for (int i = 0; i < n; i++)
  2271.                 made[i] = cur[i];
  2272.             int t1 = clock();
  2273.             radixsortmsd(made, made + n);
  2274.             int t2 = clock();
  2275.             if (!check(n)) printf("incorrect");
  2276.             else printf("%d", t2 - t1);
  2277.             if (run != 20) printf(" ");
  2278.             else printf("\n");
  2279.         }
  2280.     }
  2281.     fclose(stdout);
  2282.     output = "Results\\Swaps\\quicksort1e7.txt";
  2283.     freopen(output.c_str(), "w", stdout);
  2284.     for (int t = 56; t <= 90; t++) {
  2285.         int n = read("Swaps\\test" + to_string(t) + ".txt");
  2286.         for (int run = 1; run <= 20; run++) {
  2287.             for (int i = 0; i < n; i++)
  2288.                 made[i] = cur[i];
  2289.             int t1 = clock();
  2290.             quicksort(made, made + n);
  2291.             int t2 = clock();
  2292.             if (!check(n)) printf("incorrect");
  2293.             else printf("%d", t2 - t1);
  2294.             if (run != 20) printf(" ");
  2295.             else printf("\n");
  2296.         }
  2297.     }
  2298.     fclose(stdout);
  2299.     output = "Results\\Swaps\\quickinssort1e7.txt";
  2300.     freopen(output.c_str(), "w", stdout);
  2301.     for (int t = 56; t <= 90; t++) {
  2302.         int n = read("Swaps\\test" + to_string(t) + ".txt");
  2303.         for (int run = 1; run <= 20; run++) {
  2304.             for (int i = 0; i < n; i++)
  2305.                 made[i] = cur[i];
  2306.             int t1 = clock();
  2307.             quickinssort(made, made + n);
  2308.             int t2 = clock();
  2309.             if (!check(n)) printf("incorrect");
  2310.             else printf("%d", t2 - t1);
  2311.             if (run != 20) printf(" ");
  2312.             else printf("\n");
  2313.         }
  2314.     }
  2315.     fclose(stdout);
  2316.     output = "Results\\Swaps\\mergeinssort1e7.txt";
  2317.     freopen(output.c_str(), "w", stdout);
  2318.     for (int t = 56; t <= 90; t++) {
  2319.         int n = read("Swaps\\test" + to_string(t) + ".txt");
  2320.         for (int run = 1; run <= 20; run++) {
  2321.             for (int i = 0; i < n; i++)
  2322.                 made[i] = cur[i];
  2323.             int t1 = clock();
  2324.             mergeinssort(made, made + n);
  2325.             int t2 = clock();
  2326.             if (!check(n)) printf("incorrect");
  2327.             else printf("%d", t2 - t1);
  2328.             if (run != 20) printf(" ");
  2329.             else printf("\n");
  2330.         }
  2331.     }
  2332.     fclose(stdout);
  2333.     output = "Results\\Swaps\\radixsortmsd1e7.txt";
  2334.     freopen(output.c_str(), "w", stdout);
  2335.     for (int t = 56; t <= 90; t++) {
  2336.         int n = read("Swaps\\test" + to_string(t) + ".txt");
  2337.         for (int run = 1; run <= 20; run++) {
  2338.             for (int i = 0; i < n; i++)
  2339.                 made[i] = cur[i];
  2340.             int t1 = clock();
  2341.             radixsortmsd(made, made + n);
  2342.             int t2 = clock();
  2343.             if (!check(n)) printf("incorrect");
  2344.             else printf("%d", t2 - t1);
  2345.             if (run != 20) printf(" ");
  2346.             else printf("\n");
  2347.         }
  2348.     }
  2349.     fclose(stdout);
  2350.     output = "Results\\Swaps\\quicksort1e8.txt";
  2351.     freopen(output.c_str(), "w", stdout);
  2352.     for (int t = 91; t <= 130; t++) {
  2353.         int n = read("Swaps\\test" + to_string(t) + ".txt");
  2354.         for (int run = 1; run <= 20; run++) {
  2355.             for (int i = 0; i < n; i++)
  2356.                 made[i] = cur[i];
  2357.             int t1 = clock();
  2358.             quicksort(made, made + n);
  2359.             int t2 = clock();
  2360.             if (!check(n)) printf("incorrect");
  2361.             else printf("%d", t2 - t1);
  2362.             if (run != 20) printf(" ");
  2363.             else printf("\n");
  2364.         }
  2365.     }
  2366.     fclose(stdout);
  2367.     output = "Results\\Swaps\\quickinssort1e8.txt";
  2368.     freopen(output.c_str(), "w", stdout);
  2369.     for (int t = 91; t <= 130; t++) {
  2370.         int n = read("Swaps\\test" + to_string(t) + ".txt");
  2371.         for (int run = 1; run <= 20; run++) {
  2372.             for (int i = 0; i < n; i++)
  2373.                 made[i] = cur[i];
  2374.             int t1 = clock();
  2375.             quickinssort(made, made + n);
  2376.             int t2 = clock();
  2377.             if (!check(n)) printf("incorrect");
  2378.             else printf("%d", t2 - t1);
  2379.             if (run != 20) printf(" ");
  2380.             else printf("\n");
  2381.         }
  2382.     }
  2383.     fclose(stdout);
  2384.     output = "Results\\Swaps\\mergeinssort1e8.txt";
  2385.     freopen(output.c_str(), "w", stdout);
  2386.     for (int t = 91; t <= 130; t++) {
  2387.         int n = read("Swaps\\test" + to_string(t) + ".txt");
  2388.         for (int run = 1; run <= 20; run++) {
  2389.             for (int i = 0; i < n; i++)
  2390.                 made[i] = cur[i];
  2391.             int t1 = clock();
  2392.             mergeinssort(made, made + n);
  2393.             int t2 = clock();
  2394.             if (!check(n)) printf("incorrect");
  2395.             else printf("%d", t2 - t1);
  2396.             if (run != 20) printf(" ");
  2397.             else printf("\n");
  2398.         }
  2399.     }
  2400.     fclose(stdout);
  2401.     output = "Results\\Swaps\\radixsortmsd1e8.txt";
  2402.     freopen(output.c_str(), "w", stdout);
  2403.     for (int t = 91; t <= 130; t++) {
  2404.         int n = read("Swaps\\test" + to_string(t) + ".txt");
  2405.         for (int run = 1; run <= 20; run++) {
  2406.             for (int i = 0; i < n; i++)
  2407.                 made[i] = cur[i];
  2408.             int t1 = clock();
  2409.             radixsortmsd(made, made + n);
  2410.             int t2 = clock();
  2411.             if (!check(n)) printf("incorrect");
  2412.             else printf("%d", t2 - t1);
  2413.             if (run != 20) printf(" ");
  2414.             else printf("\n");
  2415.         }
  2416.     }
  2417.     fclose(stdout);
  2418.     output = "Results\\Additional\\combsort1e7.txt";
  2419.     freopen(output.c_str(), "w", stdout);
  2420.     for (int t = 65; t <= 99; t++) {
  2421.         int n = read("Additional\\test" + to_string(t) + ".txt");
  2422.         for (int run = 1; run <= 20; run++) {
  2423.             for (int i = 0; i < n; i++)
  2424.                 made[i] = cur[i];
  2425.             int t1 = clock();
  2426.             combsort(made, made + n);
  2427.             int t2 = clock();
  2428.             if (!check(n)) printf("incorrect");
  2429.             else printf("%d", t2 - t1);
  2430.             if (run != 20) printf(" ");
  2431.             else printf("\n");
  2432.         }
  2433.     }
  2434.     fclose(stdout);
  2435.     output = "Results\\Additional\\quicksort1e7.txt";
  2436.     freopen(output.c_str(), "w", stdout);
  2437.     for (int t = 65; t <= 99; t++) {
  2438.         int n = read("Additional\\test" + to_string(t) + ".txt");
  2439.         for (int run = 1; run <= 20; run++) {
  2440.             for (int i = 0; i < n; i++)
  2441.                 made[i] = cur[i];
  2442.             int t1 = clock();
  2443.             quicksort(made, made + n);
  2444.             int t2 = clock();
  2445.             if (!check(n)) printf("incorrect");
  2446.             else printf("%d", t2 - t1);
  2447.             if (run != 20) printf(" ");
  2448.             else printf("\n");
  2449.         }
  2450.     }
  2451.     fclose(stdout);
  2452.     output = "Results\\Additional\\quickinssort1e7.txt";
  2453.     freopen(output.c_str(), "w", stdout);
  2454.     for (int t = 65; t <= 99; t++) {
  2455.         int n = read("Additional\\test" + to_string(t) + ".txt");
  2456.         for (int run = 1; run <= 20; run++) {
  2457.             for (int i = 0; i < n; i++)
  2458.                 made[i] = cur[i];
  2459.             int t1 = clock();
  2460.             quickinssort(made, made + n);
  2461.             int t2 = clock();
  2462.             if (!check(n)) printf("incorrect");
  2463.             else printf("%d", t2 - t1);
  2464.             if (run != 20) printf(" ");
  2465.             else printf("\n");
  2466.         }
  2467.     }
  2468.     fclose(stdout);
  2469.     output = "Results\\Additional\\mergeinssort1e7.txt";
  2470.     freopen(output.c_str(), "w", stdout);
  2471.     for (int t = 65; t <= 99; t++) {
  2472.         int n = read("Additional\\test" + to_string(t) + ".txt");
  2473.         for (int run = 1; run <= 20; run++) {
  2474.             for (int i = 0; i < n; i++)
  2475.                 made[i] = cur[i];
  2476.             int t1 = clock();
  2477.             mergeinssort(made, made + n);
  2478.             int t2 = clock();
  2479.             if (!check(n)) printf("incorrect");
  2480.             else printf("%d", t2 - t1);
  2481.             if (run != 20) printf(" ");
  2482.             else printf("\n");
  2483.         }
  2484.     }
  2485.     fclose(stdout);
  2486.     output = "Results\\Additional\\radixsortmsd1e7.txt";
  2487.     freopen(output.c_str(), "w", stdout);
  2488.     for (int t = 65; t <= 99; t++) {
  2489.         int n = read("Additional\\test" + to_string(t) + ".txt");
  2490.         for (int run = 1; run <= 20; run++) {
  2491.             for (int i = 0; i < n; i++)
  2492.                 made[i] = cur[i];
  2493.             int t1 = clock();
  2494.             radixsortmsd(made, made + n);
  2495.             int t2 = clock();
  2496.             if (!check(n)) printf("incorrect");
  2497.             else printf("%d", t2 - t1);
  2498.             if (run != 20) printf(" ");
  2499.             else printf("\n");
  2500.         }
  2501.     }
  2502.     fclose(stdout);
  2503.     output = "Results\\Additional\\quicksort1e8.txt";
  2504.     freopen(output.c_str(), "w", stdout);
  2505.     for (int t = 100; t <= 136; t++) {
  2506.         int n = read("Additional\\test" + to_string(t) + ".txt");
  2507.         for (int run = 1; run <= 20; run++) {
  2508.             for (int i = 0; i < n; i++)
  2509.                 made[i] = cur[i];
  2510.             int t1 = clock();
  2511.             quicksort(made, made + n);
  2512.             int t2 = clock();
  2513.             if (!check(n)) printf("incorrect");
  2514.             else printf("%d", t2 - t1);
  2515.             if (run != 20) printf(" ");
  2516.             else printf("\n");
  2517.         }
  2518.     }
  2519.     fclose(stdout);
  2520.     output = "Results\\Additional\\quickinssort1e8.txt";
  2521.     freopen(output.c_str(), "w", stdout);
  2522.     for (int t = 100; t <= 136; t++) {
  2523.         int n = read("Additional\\test" + to_string(t) + ".txt");
  2524.         for (int run = 1; run <= 20; run++) {
  2525.             for (int i = 0; i < n; i++)
  2526.                 made[i] = cur[i];
  2527.             int t1 = clock();
  2528.             quickinssort(made, made + n);
  2529.             int t2 = clock();
  2530.             if (!check(n)) printf("incorrect");
  2531.             else printf("%d", t2 - t1);
  2532.             if (run != 20) printf(" ");
  2533.             else printf("\n");
  2534.         }
  2535.     }
  2536.     fclose(stdout);
  2537.     output = "Results\\Additional\\mergeinssort1e8.txt";
  2538.     freopen(output.c_str(), "w", stdout);
  2539.     for (int t = 100; t <= 136; t++) {
  2540.         int n = read("Additional\\test" + to_string(t) + ".txt");
  2541.         for (int run = 1; run <= 20; run++) {
  2542.             for (int i = 0; i < n; i++)
  2543.                 made[i] = cur[i];
  2544.             int t1 = clock();
  2545.             mergeinssort(made, made + n);
  2546.             int t2 = clock();
  2547.             if (!check(n)) printf("incorrect");
  2548.             else printf("%d", t2 - t1);
  2549.             if (run != 20) printf(" ");
  2550.             else printf("\n");
  2551.         }
  2552.     }
  2553.     fclose(stdout);
  2554.     output = "Results\\Additional\\radixsortmsd1e8.txt";
  2555.     freopen(output.c_str(), "w", stdout);
  2556.     for (int t = 100; t <= 136; t++) {
  2557.         int n = read("Additional\\test" + to_string(t) + ".txt");
  2558.         for (int run = 1; run <= 20; run++) {
  2559.             for (int i = 0; i < n; i++)
  2560.                 made[i] = cur[i];
  2561.             int t1 = clock();
  2562.             radixsortmsd(made, made + n);
  2563.             int t2 = clock();
  2564.             if (!check(n)) printf("incorrect");
  2565.             else printf("%d", t2 - t1);
  2566.             if (run != 20) printf(" ");
  2567.             else printf("\n");
  2568.         }
  2569.     }
  2570.     fclose(stdout);
  2571. }
  2572. void fulltest1() {
  2573.     // Random
  2574.     // 1 - 30   : 10^5
  2575.     // 31 - 60  : 10^6
  2576.     // 61 - 90  : 10^7
  2577.     // 91 - 120 : 10^8
  2578.  
  2579.     string input, output;
  2580.     int n, t1, t2;
  2581.  
  2582.     for (int t = 1; t <= 30; t++) {
  2583.         n = read("Random\\test" + to_string(t) + ".txt");
  2584.         for (int run = 1; run <= 20; run++) {
  2585.             for (int i = 0; i < n; i++)
  2586.                 made[i] = cur[i];
  2587.             t1 = clock();
  2588.             bubblesort(made, made + n);
  2589.             t2 = clock();
  2590.             output = "Results\\Random\\bubblesort1e5.txt";
  2591.             freopen(output.c_str(), "a", stdout);
  2592.             if (!check(n)) printf("incorrect");
  2593.             else printf("%d", t2 - t1);
  2594.             if (run != 20) printf(" ");
  2595.             else printf("\n");
  2596.             fclose(stdout);
  2597.         }
  2598.         for (int run = 1; run <= 20; run++) {
  2599.             for (int i = 0; i < n; i++)
  2600.                 made[i] = cur[i];
  2601.             t1 = clock();
  2602.             shakersort(made, made + n);
  2603.             t2 = clock();
  2604.             output = "Results\\Random\\shakersort1e5.txt";
  2605.             freopen(output.c_str(), "a", stdout);
  2606.             if (!check(n)) printf("incorrect");
  2607.             else printf("%d", t2 - t1);
  2608.             if (run != 20) printf(" ");
  2609.             else printf("\n");
  2610.             fclose(stdout);
  2611.         }
  2612.         for (int run = 1; run <= 20; run++) {
  2613.             for (int i = 0; i < n; i++)
  2614.                 made[i] = cur[i];
  2615.             t1 = clock();
  2616.             selectionsort(made, made + n);
  2617.             t2 = clock();
  2618.             output = "Results\\Random\\selectionsort1e5.txt";
  2619.             freopen(output.c_str(), "a", stdout);
  2620.             if (!check(n)) printf("incorrect");
  2621.             else printf("%d", t2 - t1);
  2622.             if (run != 20) printf(" ");
  2623.             else printf("\n");
  2624.             fclose(stdout);
  2625.         }
  2626.         for (int run = 1; run <= 20; run++) {
  2627.             for (int i = 0; i < n; i++)
  2628.                 made[i] = cur[i];
  2629.             t1 = clock();
  2630.             insertionsort(made, made + n);
  2631.             t2 = clock();
  2632.             output = "Results\\Random\\insertionsort1e5.txt";
  2633.             freopen(output.c_str(), "a", stdout);
  2634.             if (!check(n)) printf("incorrect");
  2635.             else printf("%d", t2 - t1);
  2636.             if (run != 20) printf(" ");
  2637.             else printf("\n");
  2638.             fclose(stdout);
  2639.         }
  2640.         for (int run = 1; run <= 20; run++) {
  2641.             for (int i = 0; i < n; i++)
  2642.                 made[i] = cur[i];
  2643.             t1 = clock();
  2644.             gnomesort(made, made + n);
  2645.             t2 = clock();
  2646.             output = "Results\\Random\\gnomesort1e5.txt";
  2647.             freopen(output.c_str(), "a", stdout);
  2648.             if (!check(n)) printf("incorrect");
  2649.             else printf("%d", t2 - t1);
  2650.             if (run != 20) printf(" ");
  2651.             else printf("\n");
  2652.             fclose(stdout);
  2653.         }
  2654.     }
  2655.     for (int t = 31; t <= 60; t++) {
  2656.         n = read("Random\\test" + to_string(t) + ".txt");
  2657.         for (int run = 1; run <= 20; run++) {
  2658.             for (int i = 0; i < n; i++)
  2659.                 made[i] = cur[i];
  2660.             t1 = clock();
  2661.             bitonicsort(made, made + n);
  2662.             t2 = clock();
  2663.             output = "Results\\Random\\bitonicsort1e6.txt";
  2664.             freopen(output.c_str(), "a", stdout);
  2665.             if (!check(n)) printf("incorrect");
  2666.             else printf("%d", t2 - t1);
  2667.             if (run != 20) printf(" ");
  2668.             else printf("\n");
  2669.             fclose(stdout);
  2670.         }
  2671.         for (int run = 1; run <= 20; run++) {
  2672.             for (int i = 0; i < n; i++)
  2673.                 made[i] = cur[i];
  2674.             t1 = clock();
  2675.             treesort(made, made + n);
  2676.             t2 = clock();
  2677.             output = "Results\\Random\\treesort1e6.txt";
  2678.             freopen(output.c_str(), "a", stdout);
  2679.             if (!check(n)) printf("incorrect");
  2680.             else printf("%d", t2 - t1);
  2681.             if (run != 20) printf(" ");
  2682.             else printf("\n");
  2683.             fclose(stdout);
  2684.         }
  2685.         for (int run = 1; run <= 20; run++) {
  2686.             for (int i = 0; i < n; i++)
  2687.                 made[i] = cur[i];
  2688.             t1 = clock();
  2689.             shellsorthib(made, made + n);
  2690.             t2 = clock();
  2691.             output = "Results\\Random\\shellsorthib1e6.txt";
  2692.             freopen(output.c_str(), "a", stdout);
  2693.             if (!check(n)) printf("incorrect");
  2694.             else printf("%d", t2 - t1);
  2695.             if (run != 20) printf(" ");
  2696.             else printf("\n");
  2697.             fclose(stdout);
  2698.         }
  2699.         for (int run = 1; run <= 20; run++) {
  2700.             for (int i = 0; i < n; i++)
  2701.                 made[i] = cur[i];
  2702.             t1 = clock();
  2703.             shellsortpratt(made, made + n);
  2704.             t2 = clock();
  2705.             output = "Results\\Random\\shellsortpratt1e6.txt";
  2706.             freopen(output.c_str(), "a", stdout);
  2707.             if (!check(n)) printf("incorrect");
  2708.             else printf("%d", t2 - t1);
  2709.             if (run != 20) printf(" ");
  2710.             else printf("\n");
  2711.             fclose(stdout);
  2712.         }
  2713.     }
  2714.     for (int t = 61; t <= 90; t++) {
  2715.         n = read("Random\\test" + to_string(t) + ".txt");
  2716.         for (int run = 1; run <= 20; run++) {
  2717.             for (int i = 0; i < n; i++)
  2718.                 made[i] = cur[i];
  2719.             t1 = clock();
  2720.             bitonicsort(made, made + n);
  2721.             t2 = clock();
  2722.             output = "Results\\Random\\bitonicsort1e7.txt";
  2723.             freopen(output.c_str(), "a", stdout);
  2724.             if (!check(n)) printf("incorrect");
  2725.             else printf("%d", t2 - t1);
  2726.             if (run != 20) printf(" ");
  2727.             else printf("\n");
  2728.             fclose(stdout);
  2729.         }
  2730.         for (int run = 1; run <= 20; run++) {
  2731.             for (int i = 0; i < n; i++)
  2732.                 made[i] = cur[i];
  2733.             t1 = clock();
  2734.             treesort(made, made + n);
  2735.             t2 = clock();
  2736.             output = "Results\\Random\\treesort1e7.txt";
  2737.             freopen(output.c_str(), "a", stdout);
  2738.             if (!check(n)) printf("incorrect");
  2739.             else printf("%d", t2 - t1);
  2740.             if (run != 20) printf(" ");
  2741.             else printf("\n");
  2742.             fclose(stdout);
  2743.         }
  2744.         for (int run = 1; run <= 20; run++) {
  2745.             for (int i = 0; i < n; i++)
  2746.                 made[i] = cur[i];
  2747.             t1 = clock();
  2748.             shellsorthib(made, made + n);
  2749.             t2 = clock();
  2750.             output = "Results\\Random\\shellsorthib1e7.txt";
  2751.             freopen(output.c_str(), "a", stdout);
  2752.             if (!check(n)) printf("incorrect");
  2753.             else printf("%d", t2 - t1);
  2754.             if (run != 20) printf(" ");
  2755.             else printf("\n");
  2756.             fclose(stdout);
  2757.         }
  2758.         for (int run = 1; run <= 20; run++) {
  2759.             for (int i = 0; i < n; i++)
  2760.                 made[i] = cur[i];
  2761.             t1 = clock();
  2762.             shellsortpratt(made, made + n);
  2763.             t2 = clock();
  2764.             output = "Results\\Random\\shellsortpratt1e7.txt";
  2765.             freopen(output.c_str(), "a", stdout);
  2766.             if (!check(n)) printf("incorrect");
  2767.             else printf("%d", t2 - t1);
  2768.             if (run != 20) printf(" ");
  2769.             else printf("\n");
  2770.             fclose(stdout);
  2771.         }
  2772.     }
  2773.     for (int t = 61; t <= 90; t++) {
  2774.         n = read("Random\\test" + to_string(t) + ".txt");
  2775.         for (int run = 1; run <= 20; run++) {
  2776.             for (int i = 0; i < n; i++)
  2777.                 made[i] = cur[i];
  2778.             t1 = clock();
  2779.             combsort(made, made + n);
  2780.             t2 = clock();
  2781.             output = "Results\\Random\\combsort1e7.txt";
  2782.             freopen(output.c_str(), "a", stdout);
  2783.             if (!check(n)) printf("incorrect");
  2784.             else printf("%d", t2 - t1);
  2785.             if (run != 20) printf(" ");
  2786.             else printf("\n");
  2787.             fclose(stdout);
  2788.         }
  2789.         for (int run = 1; run <= 20; run++) {
  2790.             for (int i = 0; i < n; i++)
  2791.                 made[i] = cur[i];
  2792.             t1 = clock();
  2793.             newbucketsort(made, made + n);
  2794.             t2 = clock();
  2795.             output = "Results\\Random\\bucketsort1e7.txt";
  2796.             freopen(output.c_str(), "a", stdout);
  2797.             if (!check(n)) printf("incorrect");
  2798.             else printf("%d", t2 - t1);
  2799.             if (run != 20) printf(" ");
  2800.             else printf("\n");
  2801.             fclose(stdout);
  2802.         }
  2803.         for (int run = 1; run <= 20; run++) {
  2804.             for (int i = 0; i < n; i++)
  2805.                 made[i] = cur[i];
  2806.             t1 = clock();
  2807.             heapsort(made, made + n);
  2808.             t2 = clock();
  2809.             output = "Results\\Random\\heapsort1e7.txt";
  2810.             freopen(output.c_str(), "a", stdout);
  2811.             if (!check(n)) printf("incorrect");
  2812.             else printf("%d", t2 - t1);
  2813.             if (run != 20) printf(" ");
  2814.             else printf("\n");
  2815.             fclose(stdout);
  2816.         }
  2817.         for (int run = 1; run <= 20; run++) {
  2818.             for (int i = 0; i < n; i++)
  2819.                 made[i] = cur[i];
  2820.             t1 = clock();
  2821.             sort(made, made + n);
  2822.             t2 = clock();
  2823.             output = "Results\\Random\\stlsort1e7.txt";
  2824.             freopen(output.c_str(), "a", stdout);
  2825.             if (!check(n)) printf("incorrect");
  2826.             else printf("%d", t2 - t1);
  2827.             if (run != 20) printf(" ");
  2828.             else printf("\n");
  2829.             fclose(stdout);
  2830.         }
  2831.         for (int run = 1; run <= 20; run++) {
  2832.             for (int i = 0; i < n; i++)
  2833.                 made[i] = cur[i];
  2834.             t1 = clock();
  2835.             quicksort(made, made + n);
  2836.             t2 = clock();
  2837.             output = "Results\\Random\\quicksort1e7.txt";
  2838.             freopen(output.c_str(), "a", stdout);
  2839.             if (!check(n)) printf("incorrect");
  2840.             else printf("%d", t2 - t1);
  2841.             if (run != 20) printf(" ");
  2842.             else printf("\n");
  2843.             fclose(stdout);
  2844.         }
  2845.         for (int run = 1; run <= 20; run++) {
  2846.             for (int i = 0; i < n; i++)
  2847.                 made[i] = cur[i];
  2848.             t1 = clock();
  2849.             quickinssort(made, made + n);
  2850.             t2 = clock();
  2851.             output = "Results\\Random\\quickinssort1e7.txt";
  2852.             freopen(output.c_str(), "a", stdout);
  2853.             if (!check(n)) printf("incorrect");
  2854.             else printf("%d", t2 - t1);
  2855.             if (run != 20) printf(" ");
  2856.             else printf("\n");
  2857.             fclose(stdout);
  2858.         }
  2859.         for (int run = 1; run <= 20; run++) {
  2860.             for (int i = 0; i < n; i++)
  2861.                 made[i] = cur[i];
  2862.             t1 = clock();
  2863.             mergesort(made, made + n);
  2864.             t2 = clock();
  2865.             output = "Results\\Random\\mergesort1e7.txt";
  2866.             freopen(output.c_str(), "a", stdout);
  2867.             if (!check(n)) printf("incorrect");
  2868.             else printf("%d", t2 - t1);
  2869.             if (run != 20) printf(" ");
  2870.             else printf("\n");
  2871.             fclose(stdout);
  2872.         }
  2873.         for (int run = 1; run <= 20; run++) {
  2874.             for (int i = 0; i < n; i++)
  2875.                 made[i] = cur[i];
  2876.             t1 = clock();
  2877.             mergeinssort(made, made + n);
  2878.             t2 = clock();
  2879.             output = "Results\\Random\\mergeinssort1e7.txt";
  2880.             freopen(output.c_str(), "a", stdout);
  2881.             if (!check(n)) printf("incorrect");
  2882.             else printf("%d", t2 - t1);
  2883.             if (run != 20) printf(" ");
  2884.             else printf("\n");
  2885.             fclose(stdout);
  2886.         }
  2887.         for (int run = 1; run <= 20; run++) {
  2888.             for (int i = 0; i < n; i++)
  2889.                 made[i] = cur[i];
  2890.             t1 = clock();
  2891.             shellsort(made, made + n);
  2892.             t2 = clock();
  2893.             output = "Results\\Random\\shellsort1e7.txt";
  2894.             freopen(output.c_str(), "a", stdout);
  2895.             if (!check(n)) printf("incorrect");
  2896.             else printf("%d", t2 - t1);
  2897.             if (run != 20) printf(" ");
  2898.             else printf("\n");
  2899.             fclose(stdout);
  2900.         }
  2901.         for (int run = 1; run <= 20; run++) {
  2902.             for (int i = 0; i < n; i++)
  2903.                 made[i] = cur[i];
  2904.             t1 = clock();
  2905.             shellsortsedgwick(made, made + n);
  2906.             t2 = clock();
  2907.             output = "Results\\Random\\shellsortsedgwick1e7.txt";
  2908.             freopen(output.c_str(), "a", stdout);
  2909.             if (!check(n)) printf("incorrect");
  2910.             else printf("%d", t2 - t1);
  2911.             if (run != 20) printf(" ");
  2912.             else printf("\n");
  2913.             fclose(stdout);
  2914.         }
  2915.         for (int run = 1; run <= 20; run++) {
  2916.             for (int i = 0; i < n; i++)
  2917.                 made[i] = cur[i];
  2918.             t1 = clock();
  2919.             radixsort(made, made + n);
  2920.             t2 = clock();
  2921.             output = "Results\\Random\\radixsort1e7.txt";
  2922.             freopen(output.c_str(), "a", stdout);
  2923.             if (!check(n)) printf("incorrect");
  2924.             else printf("%d", t2 - t1);
  2925.             if (run != 20) printf(" ");
  2926.             else printf("\n");
  2927.             fclose(stdout);
  2928.         }
  2929.         for (int run = 1; run <= 20; run++) {
  2930.             for (int i = 0; i < n; i++)
  2931.                 made[i] = cur[i];
  2932.             t1 = clock();
  2933.             timsort(made, made + n);
  2934.             t2 = clock();
  2935.             output = "Results\\Random\\timsort1e7.txt";
  2936.             freopen(output.c_str(), "a", stdout);
  2937.             if (!check(n)) printf("incorrect");
  2938.             else printf("%d", t2 - t1);
  2939.             if (run != 20) printf(" ");
  2940.             else printf("\n");
  2941.             fclose(stdout);
  2942.         }
  2943.         for (int run = 1; run <= 20; run++) {
  2944.             for (int i = 0; i < n; i++)
  2945.                 made[i] = cur[i];
  2946.             t1 = clock();
  2947.             myshell1(made, made + n);
  2948.             t2 = clock();
  2949.             output = "Results\\Random\\myshell1_1e7.txt";
  2950.             freopen(output.c_str(), "a", stdout);
  2951.             if (!check(n)) printf("incorrect");
  2952.             else printf("%d", t2 - t1);
  2953.             if (run != 20) printf(" ");
  2954.             else printf("\n");
  2955.             fclose(stdout);
  2956.         }
  2957.         for (int run = 1; run <= 20; run++) {
  2958.             for (int i = 0; i < n; i++)
  2959.                 made[i] = cur[i];
  2960.             t1 = clock();
  2961.             myshell2(made, made + n);
  2962.             t2 = clock();
  2963.             output = "Results\\Random\\myshell2_1e7.txt";
  2964.             freopen(output.c_str(), "a", stdout);
  2965.             if (!check(n)) printf("incorrect");
  2966.             else printf("%d", t2 - t1);
  2967.             if (run != 20) printf(" ");
  2968.             else printf("\n");
  2969.             fclose(stdout);
  2970.         }
  2971.         for (int run = 1; run <= 20; run++) {
  2972.             for (int i = 0; i < n; i++)
  2973.                 made[i] = cur[i];
  2974.             t1 = clock();
  2975.             myshell3(made, made + n);
  2976.             t2 = clock();
  2977.             output = "Results\\Random\\myshell3_1e7.txt";
  2978.             freopen(output.c_str(), "a", stdout);
  2979.             if (!check(n)) printf("incorrect");
  2980.             else printf("%d", t2 - t1);
  2981.             if (run != 20) printf(" ");
  2982.             else printf("\n");
  2983.             fclose(stdout);
  2984.         }
  2985.     }
  2986.     for (int t = 91; t <= 120; t++) {
  2987.         n = read("Random\\test" + to_string(t) + ".txt");
  2988.         for (int run = 1; run <= 20; run++) {
  2989.             for (int i = 0; i < n; i++)
  2990.                 made[i] = cur[i];
  2991.             t1 = clock();
  2992.             combsort(made, made + n);
  2993.             t2 = clock();
  2994.             output = "Results\\Random\\combsort1e8.txt";
  2995.             freopen(output.c_str(), "a", stdout);
  2996.             if (!check(n)) printf("incorrect");
  2997.             else printf("%d", t2 - t1);
  2998.             if (run != 20) printf(" ");
  2999.             else printf("\n");
  3000.             fclose(stdout);
  3001.         }
  3002.         for (int run = 1; run <= 20; run++) {
  3003.             for (int i = 0; i < n; i++)
  3004.                 made[i] = cur[i];
  3005.             t1 = clock();
  3006.             newbucketsort(made, made + n);
  3007.             t2 = clock();
  3008.             output = "Results\\Random\\bucketsort1e8.txt";
  3009.             freopen(output.c_str(), "a", stdout);
  3010.             if (!check(n)) printf("incorrect");
  3011.             else printf("%d", t2 - t1);
  3012.             if (run != 20) printf(" ");
  3013.             else printf("\n");
  3014.             fclose(stdout);
  3015.         }
  3016.         for (int run = 1; run <= 20; run++) {
  3017.             for (int i = 0; i < n; i++)
  3018.                 made[i] = cur[i];
  3019.             t1 = clock();
  3020.             heapsort(made, made + n);
  3021.             t2 = clock();
  3022.             output = "Results\\Random\\heapsort1e8.txt";
  3023.             freopen(output.c_str(), "a", stdout);
  3024.             if (!check(n)) printf("incorrect");
  3025.             else printf("%d", t2 - t1);
  3026.             if (run != 20) printf(" ");
  3027.             else printf("\n");
  3028.             fclose(stdout);
  3029.         }
  3030.         for (int run = 1; run <= 20; run++) {
  3031.             for (int i = 0; i < n; i++)
  3032.                 made[i] = cur[i];
  3033.             t1 = clock();
  3034.             sort(made, made + n);
  3035.             t2 = clock();
  3036.             output = "Results\\Random\\stlsort1e8.txt";
  3037.             freopen(output.c_str(), "a", stdout);
  3038.             if (!check(n)) printf("incorrect");
  3039.             else printf("%d", t2 - t1);
  3040.             if (run != 20) printf(" ");
  3041.             else printf("\n");
  3042.             fclose(stdout);
  3043.         }
  3044.         for (int run = 1; run <= 20; run++) {
  3045.             for (int i = 0; i < n; i++)
  3046.                 made[i] = cur[i];
  3047.             t1 = clock();
  3048.             quicksort(made, made + n);
  3049.             t2 = clock();
  3050.             output = "Results\\Random\\quicksort1e8.txt";
  3051.             freopen(output.c_str(), "a", stdout);
  3052.             if (!check(n)) printf("incorrect");
  3053.             else printf("%d", t2 - t1);
  3054.             if (run != 20) printf(" ");
  3055.             else printf("\n");
  3056.             fclose(stdout);
  3057.         }
  3058.         for (int run = 1; run <= 20; run++) {
  3059.             for (int i = 0; i < n; i++)
  3060.                 made[i] = cur[i];
  3061.             t1 = clock();
  3062.             quickinssort(made, made + n);
  3063.             t2 = clock();
  3064.             output = "Results\\Random\\quickinssort1e8.txt";
  3065.             freopen(output.c_str(), "a", stdout);
  3066.             if (!check(n)) printf("incorrect");
  3067.             else printf("%d", t2 - t1);
  3068.             if (run != 20) printf(" ");
  3069.             else printf("\n");
  3070.             fclose(stdout);
  3071.         }
  3072.         for (int run = 1; run <= 20; run++) {
  3073.             for (int i = 0; i < n; i++)
  3074.                 made[i] = cur[i];
  3075.             t1 = clock();
  3076.             mergesort(made, made + n);
  3077.             t2 = clock();
  3078.             output = "Results\\Random\\mergesort1e8.txt";
  3079.             freopen(output.c_str(), "a", stdout);
  3080.             if (!check(n)) printf("incorrect");
  3081.             else printf("%d", t2 - t1);
  3082.             if (run != 20) printf(" ");
  3083.             else printf("\n");
  3084.             fclose(stdout);
  3085.         }
  3086.         for (int run = 1; run <= 20; run++) {
  3087.             for (int i = 0; i < n; i++)
  3088.                 made[i] = cur[i];
  3089.             t1 = clock();
  3090.             mergeinssort(made, made + n);
  3091.             t2 = clock();
  3092.             output = "Results\\Random\\mergeinssort1e8.txt";
  3093.             freopen(output.c_str(), "a", stdout);
  3094.             if (!check(n)) printf("incorrect");
  3095.             else printf("%d", t2 - t1);
  3096.             if (run != 20) printf(" ");
  3097.             else printf("\n");
  3098.             fclose(stdout);
  3099.         }
  3100.         for (int run = 1; run <= 20; run++) {
  3101.             for (int i = 0; i < n; i++)
  3102.                 made[i] = cur[i];
  3103.             t1 = clock();
  3104.             shellsort(made, made + n);
  3105.             t2 = clock();
  3106.             output = "Results\\Random\\shellsort1e8.txt";
  3107.             freopen(output.c_str(), "a", stdout);
  3108.             if (!check(n)) printf("incorrect");
  3109.             else printf("%d", t2 - t1);
  3110.             if (run != 20) printf(" ");
  3111.             else printf("\n");
  3112.             fclose(stdout);
  3113.         }
  3114.         for (int run = 1; run <= 20; run++) {
  3115.             for (int i = 0; i < n; i++)
  3116.                 made[i] = cur[i];
  3117.             t1 = clock();
  3118.             shellsortsedgwick(made, made + n);
  3119.             t2 = clock();
  3120.             output = "Results\\Random\\shellsortsedgwick1e8.txt";
  3121.             freopen(output.c_str(), "a", stdout);
  3122.             if (!check(n)) printf("incorrect");
  3123.             else printf("%d", t2 - t1);
  3124.             if (run != 20) printf(" ");
  3125.             else printf("\n");
  3126.             fclose(stdout);
  3127.         }
  3128.         for (int run = 1; run <= 20; run++) {
  3129.             for (int i = 0; i < n; i++)
  3130.                 made[i] = cur[i];
  3131.             t1 = clock();
  3132.             radixsort(made, made + n);
  3133.             t2 = clock();
  3134.             output = "Results\\Random\\radixsort1e8.txt";
  3135.             freopen(output.c_str(), "a", stdout);
  3136.             if (!check(n)) printf("incorrect");
  3137.             else printf("%d", t2 - t1);
  3138.             if (run != 20) printf(" ");
  3139.             else printf("\n");
  3140.             fclose(stdout);
  3141.         }
  3142.         for (int run = 1; run <= 20; run++) {
  3143.             for (int i = 0; i < n; i++)
  3144.                 made[i] = cur[i];
  3145.             t1 = clock();
  3146.             timsort(made, made + n);
  3147.             t2 = clock();
  3148.             output = "Results\\Random\\timsort1e8.txt";
  3149.             freopen(output.c_str(), "a", stdout);
  3150.             if (!check(n)) printf("incorrect");
  3151.             else printf("%d", t2 - t1);
  3152.             if (run != 20) printf(" ");
  3153.             else printf("\n");
  3154.             fclose(stdout);
  3155.         }
  3156.         for (int run = 1; run <= 20; run++) {
  3157.             for (int i = 0; i < n; i++)
  3158.                 made[i] = cur[i];
  3159.             t1 = clock();
  3160.             myshell1(made, made + n);
  3161.             t2 = clock();
  3162.             output = "Results\\Random\\myshell1_1e8.txt";
  3163.             freopen(output.c_str(), "a", stdout);
  3164.             if (!check(n)) printf("incorrect");
  3165.             else printf("%d", t2 - t1);
  3166.             if (run != 20) printf(" ");
  3167.             else printf("\n");
  3168.             fclose(stdout);
  3169.         }
  3170.         for (int run = 1; run <= 20; run++) {
  3171.             for (int i = 0; i < n; i++)
  3172.                 made[i] = cur[i];
  3173.             t1 = clock();
  3174.             myshell2(made, made + n);
  3175.             t2 = clock();
  3176.             output = "Results\\Random\\myshell2_1e8.txt";
  3177.             freopen(output.c_str(), "a", stdout);
  3178.             if (!check(n)) printf("incorrect");
  3179.             else printf("%d", t2 - t1);
  3180.             if (run != 20) printf(" ");
  3181.             else printf("\n");
  3182.             fclose(stdout);
  3183.         }
  3184.         for (int run = 1; run <= 20; run++) {
  3185.             for (int i = 0; i < n; i++)
  3186.                 made[i] = cur[i];
  3187.             t1 = clock();
  3188.             myshell3(made, made + n);
  3189.             t2 = clock();
  3190.             output = "Results\\Random\\myshell3_1e8.txt";
  3191.             freopen(output.c_str(), "a", stdout);
  3192.             if (!check(n)) printf("incorrect");
  3193.             else printf("%d", t2 - t1);
  3194.             if (run != 20) printf(" ");
  3195.             else printf("\n");
  3196.             fclose(stdout);
  3197.         }
  3198.     }
  3199. }
  3200. void fulltest2() {
  3201.     // Part sorted
  3202.     // 1 - 25   : 10^5
  3203.     // 26 - 55  : 10^6
  3204.     // 56 - 90  : 10^7
  3205.     // 91 - 130 : 10^8
  3206.  
  3207.     string input, output;
  3208.     int n, t1, t2;
  3209.  
  3210.     for (int t = 1; t <= 25; t++) {
  3211.         n = read("Part sorted\\test" + to_string(t) + ".txt");
  3212.         for (int run = 1; run <= 20; run++) {
  3213.             for (int i = 0; i < n; i++)
  3214.                 made[i] = cur[i];
  3215.             t1 = clock();
  3216.             bubblesort(made, made + n);
  3217.             t2 = clock();
  3218.             output = "Results\\Part sorted\\bubblesort1e5.txt";
  3219.             freopen(output.c_str(), "a", stdout);
  3220.             if (!check(n)) printf("incorrect");
  3221.             else printf("%d", t2 - t1);
  3222.             if (run != 20) printf(" ");
  3223.             else printf("\n");
  3224.             fclose(stdout);
  3225.         }
  3226.         for (int run = 1; run <= 20; run++) {
  3227.             for (int i = 0; i < n; i++)
  3228.                 made[i] = cur[i];
  3229.             t1 = clock();
  3230.             shakersort(made, made + n);
  3231.             t2 = clock();
  3232.             output = "Results\\Part sorted\\shakersort1e5.txt";
  3233.             freopen(output.c_str(), "a", stdout);
  3234.             if (!check(n)) printf("incorrect");
  3235.             else printf("%d", t2 - t1);
  3236.             if (run != 20) printf(" ");
  3237.             else printf("\n");
  3238.             fclose(stdout);
  3239.         }
  3240.         for (int run = 1; run <= 20; run++) {
  3241.             for (int i = 0; i < n; i++)
  3242.                 made[i] = cur[i];
  3243.             t1 = clock();
  3244.             selectionsort(made, made + n);
  3245.             t2 = clock();
  3246.             output = "Results\\Part sorted\\selectionsort1e5.txt";
  3247.             freopen(output.c_str(), "a", stdout);
  3248.             if (!check(n)) printf("incorrect");
  3249.             else printf("%d", t2 - t1);
  3250.             if (run != 20) printf(" ");
  3251.             else printf("\n");
  3252.             fclose(stdout);
  3253.         }
  3254.         for (int run = 1; run <= 20; run++) {
  3255.             for (int i = 0; i < n; i++)
  3256.                 made[i] = cur[i];
  3257.             t1 = clock();
  3258.             insertionsort(made, made + n);
  3259.             t2 = clock();
  3260.             output = "Results\\Part sorted\\insertionsort1e5.txt";
  3261.             freopen(output.c_str(), "a", stdout);
  3262.             if (!check(n)) printf("incorrect");
  3263.             else printf("%d", t2 - t1);
  3264.             if (run != 20) printf(" ");
  3265.             else printf("\n");
  3266.             fclose(stdout);
  3267.         }
  3268.         for (int run = 1; run <= 20; run++) {
  3269.             for (int i = 0; i < n; i++)
  3270.                 made[i] = cur[i];
  3271.             t1 = clock();
  3272.             gnomesort(made, made + n);
  3273.             t2 = clock();
  3274.             output = "Results\\Part sorted\\gnomesort1e5.txt";
  3275.             freopen(output.c_str(), "a", stdout);
  3276.             if (!check(n)) printf("incorrect");
  3277.             else printf("%d", t2 - t1);
  3278.             if (run != 20) printf(" ");
  3279.             else printf("\n");
  3280.             fclose(stdout);
  3281.         }
  3282.     }
  3283.     for (int t = 26; t <= 55; t++) {
  3284.         n = read("Part sorted\\test" + to_string(t) + ".txt");
  3285.         for (int run = 1; run <= 20; run++) {
  3286.             for (int i = 0; i < n; i++)
  3287.                 made[i] = cur[i];
  3288.             t1 = clock();
  3289.             bitonicsort(made, made + n);
  3290.             t2 = clock();
  3291.             output = "Results\\Part sorted\\bitonicsort1e6.txt";
  3292.             freopen(output.c_str(), "a", stdout);
  3293.             if (!check(n)) printf("incorrect");
  3294.             else printf("%d", t2 - t1);
  3295.             if (run != 20) printf(" ");
  3296.             else printf("\n");
  3297.             fclose(stdout);
  3298.         }
  3299.         for (int run = 1; run <= 20; run++) {
  3300.             for (int i = 0; i < n; i++)
  3301.                 made[i] = cur[i];
  3302.             t1 = clock();
  3303.             treesort(made, made + n);
  3304.             t2 = clock();
  3305.             output = "Results\\Part sorted\\treesort1e6.txt";
  3306.             freopen(output.c_str(), "a", stdout);
  3307.             if (!check(n)) printf("incorrect");
  3308.             else printf("%d", t2 - t1);
  3309.             if (run != 20) printf(" ");
  3310.             else printf("\n");
  3311.             fclose(stdout);
  3312.         }
  3313.         for (int run = 1; run <= 20; run++) {
  3314.             for (int i = 0; i < n; i++)
  3315.                 made[i] = cur[i];
  3316.             t1 = clock();
  3317.             shellsorthib(made, made + n);
  3318.             t2 = clock();
  3319.             output = "Results\\Part sorted\\shellsorthib1e6.txt";
  3320.             freopen(output.c_str(), "a", stdout);
  3321.             if (!check(n)) printf("incorrect");
  3322.             else printf("%d", t2 - t1);
  3323.             if (run != 20) printf(" ");
  3324.             else printf("\n");
  3325.             fclose(stdout);
  3326.         }
  3327.         for (int run = 1; run <= 20; run++) {
  3328.             for (int i = 0; i < n; i++)
  3329.                 made[i] = cur[i];
  3330.             t1 = clock();
  3331.             shellsortpratt(made, made + n);
  3332.             t2 = clock();
  3333.             output = "Results\\Part sorted\\shellsortpratt1e6.txt";
  3334.             freopen(output.c_str(), "a", stdout);
  3335.             if (!check(n)) printf("incorrect");
  3336.             else printf("%d", t2 - t1);
  3337.             if (run != 20) printf(" ");
  3338.             else printf("\n");
  3339.             fclose(stdout);
  3340.         }
  3341.     }
  3342.     for (int t = 56; t <= 90; t++) {
  3343.         n = read("Part sorted\\test" + to_string(t) + ".txt");
  3344.         for (int run = 1; run <= 20; run++) {
  3345.             for (int i = 0; i < n; i++)
  3346.                 made[i] = cur[i];
  3347.             t1 = clock();
  3348.             bitonicsort(made, made + n);
  3349.             t2 = clock();
  3350.             output = "Results\\Part sorted\\bitonicsort1e7.txt";
  3351.             freopen(output.c_str(), "a", stdout);
  3352.             if (!check(n)) printf("incorrect");
  3353.             else printf("%d", t2 - t1);
  3354.             if (run != 20) printf(" ");
  3355.             else printf("\n");
  3356.             fclose(stdout);
  3357.         }
  3358.         for (int run = 1; run <= 20; run++) {
  3359.             for (int i = 0; i < n; i++)
  3360.                 made[i] = cur[i];
  3361.             t1 = clock();
  3362.             treesort(made, made + n);
  3363.             t2 = clock();
  3364.             output = "Results\\Part sorted\\treesort1e7.txt";
  3365.             freopen(output.c_str(), "a", stdout);
  3366.             if (!check(n)) printf("incorrect");
  3367.             else printf("%d", t2 - t1);
  3368.             if (run != 20) printf(" ");
  3369.             else printf("\n");
  3370.             fclose(stdout);
  3371.         }
  3372.         for (int run = 1; run <= 20; run++) {
  3373.             for (int i = 0; i < n; i++)
  3374.                 made[i] = cur[i];
  3375.             t1 = clock();
  3376.             shellsorthib(made, made + n);
  3377.             t2 = clock();
  3378.             output = "Results\\Part sorted\\shellsorthib1e7.txt";
  3379.             freopen(output.c_str(), "a", stdout);
  3380.             if (!check(n)) printf("incorrect");
  3381.             else printf("%d", t2 - t1);
  3382.             if (run != 20) printf(" ");
  3383.             else printf("\n");
  3384.             fclose(stdout);
  3385.         }
  3386.         for (int run = 1; run <= 20; run++) {
  3387.             for (int i = 0; i < n; i++)
  3388.                 made[i] = cur[i];
  3389.             t1 = clock();
  3390.             shellsortpratt(made, made + n);
  3391.             t2 = clock();
  3392.             output = "Results\\Part sorted\\shellsortpratt1e7.txt";
  3393.             freopen(output.c_str(), "a", stdout);
  3394.             if (!check(n)) printf("incorrect");
  3395.             else printf("%d", t2 - t1);
  3396.             if (run != 20) printf(" ");
  3397.             else printf("\n");
  3398.             fclose(stdout);
  3399.         }
  3400.     }
  3401.     for (int t = 56; t <= 90; t++) {
  3402.         n = read("Part sorted\\test" + to_string(t) + ".txt");
  3403.         for (int run = 1; run <= 20; run++) {
  3404.             for (int i = 0; i < n; i++)
  3405.                 made[i] = cur[i];
  3406.             t1 = clock();
  3407.             combsort(made, made + n);
  3408.             t2 = clock();
  3409.             output = "Results\\Part sorted\\combsort1e7.txt";
  3410.             freopen(output.c_str(), "a", stdout);
  3411.             if (!check(n)) printf("incorrect");
  3412.             else printf("%d", t2 - t1);
  3413.             if (run != 20) printf(" ");
  3414.             else printf("\n");
  3415.             fclose(stdout);
  3416.         }
  3417.         for (int run = 1; run <= 20; run++) {
  3418.             for (int i = 0; i < n; i++)
  3419.                 made[i] = cur[i];
  3420.             t1 = clock();
  3421.             newbucketsort(made, made + n);
  3422.             t2 = clock();
  3423.             output = "Results\\Part sorted\\bucketsort1e7.txt";
  3424.             freopen(output.c_str(), "a", stdout);
  3425.             if (!check(n)) printf("incorrect");
  3426.             else printf("%d", t2 - t1);
  3427.             if (run != 20) printf(" ");
  3428.             else printf("\n");
  3429.             fclose(stdout);
  3430.         }
  3431.         for (int run = 1; run <= 20; run++) {
  3432.             for (int i = 0; i < n; i++)
  3433.                 made[i] = cur[i];
  3434.             t1 = clock();
  3435.             heapsort(made, made + n);
  3436.             t2 = clock();
  3437.             output = "Results\\Part sorted\\heapsort1e7.txt";
  3438.             freopen(output.c_str(), "a", stdout);
  3439.             if (!check(n)) printf("incorrect");
  3440.             else printf("%d", t2 - t1);
  3441.             if (run != 20) printf(" ");
  3442.             else printf("\n");
  3443.             fclose(stdout);
  3444.         }
  3445.         for (int run = 1; run <= 20; run++) {
  3446.             for (int i = 0; i < n; i++)
  3447.                 made[i] = cur[i];
  3448.             t1 = clock();
  3449.             sort(made, made + n);
  3450.             t2 = clock();
  3451.             output = "Results\\Part sorted\\stlsort1e7.txt";
  3452.             freopen(output.c_str(), "a", stdout);
  3453.             if (!check(n)) printf("incorrect");
  3454.             else printf("%d", t2 - t1);
  3455.             if (run != 20) printf(" ");
  3456.             else printf("\n");
  3457.             fclose(stdout);
  3458.         }
  3459.         for (int run = 1; run <= 20; run++) {
  3460.             for (int i = 0; i < n; i++)
  3461.                 made[i] = cur[i];
  3462.             t1 = clock();
  3463.             quicksort(made, made + n);
  3464.             t2 = clock();
  3465.             output = "Results\\Part sorted\\quicksort1e7.txt";
  3466.             freopen(output.c_str(), "a", stdout);
  3467.             if (!check(n)) printf("incorrect");
  3468.             else printf("%d", t2 - t1);
  3469.             if (run != 20) printf(" ");
  3470.             else printf("\n");
  3471.             fclose(stdout);
  3472.         }
  3473.         for (int run = 1; run <= 20; run++) {
  3474.             for (int i = 0; i < n; i++)
  3475.                 made[i] = cur[i];
  3476.             t1 = clock();
  3477.             quickinssort(made, made + n);
  3478.             t2 = clock();
  3479.             output = "Results\\Part sorted\\quickinssort1e7.txt";
  3480.             freopen(output.c_str(), "a", stdout);
  3481.             if (!check(n)) printf("incorrect");
  3482.             else printf("%d", t2 - t1);
  3483.             if (run != 20) printf(" ");
  3484.             else printf("\n");
  3485.             fclose(stdout);
  3486.         }
  3487.         for (int run = 1; run <= 20; run++) {
  3488.             for (int i = 0; i < n; i++)
  3489.                 made[i] = cur[i];
  3490.             t1 = clock();
  3491.             mergesort(made, made + n);
  3492.             t2 = clock();
  3493.             output = "Results\\Part sorted\\mergesort1e7.txt";
  3494.             freopen(output.c_str(), "a", stdout);
  3495.             if (!check(n)) printf("incorrect");
  3496.             else printf("%d", t2 - t1);
  3497.             if (run != 20) printf(" ");
  3498.             else printf("\n");
  3499.             fclose(stdout);
  3500.         }
  3501.         for (int run = 1; run <= 20; run++) {
  3502.             for (int i = 0; i < n; i++)
  3503.                 made[i] = cur[i];
  3504.             t1 = clock();
  3505.             mergeinssort(made, made + n);
  3506.             t2 = clock();
  3507.             output = "Results\\Part sorted\\mergeinssort1e7.txt";
  3508.             freopen(output.c_str(), "a", stdout);
  3509.             if (!check(n)) printf("incorrect");
  3510.             else printf("%d", t2 - t1);
  3511.             if (run != 20) printf(" ");
  3512.             else printf("\n");
  3513.             fclose(stdout);
  3514.         }
  3515.         for (int run = 1; run <= 20; run++) {
  3516.             for (int i = 0; i < n; i++)
  3517.                 made[i] = cur[i];
  3518.             t1 = clock();
  3519.             shellsort(made, made + n);
  3520.             t2 = clock();
  3521.             output = "Results\\Part sorted\\shellsort1e7.txt";
  3522.             freopen(output.c_str(), "a", stdout);
  3523.             if (!check(n)) printf("incorrect");
  3524.             else printf("%d", t2 - t1);
  3525.             if (run != 20) printf(" ");
  3526.             else printf("\n");
  3527.             fclose(stdout);
  3528.         }
  3529.         for (int run = 1; run <= 20; run++) {
  3530.             for (int i = 0; i < n; i++)
  3531.                 made[i] = cur[i];
  3532.             t1 = clock();
  3533.             shellsortsedgwick(made, made + n);
  3534.             t2 = clock();
  3535.             output = "Results\\Part sorted\\shellsortsedgwick1e7.txt";
  3536.             freopen(output.c_str(), "a", stdout);
  3537.             if (!check(n)) printf("incorrect");
  3538.             else printf("%d", t2 - t1);
  3539.             if (run != 20) printf(" ");
  3540.             else printf("\n");
  3541.             fclose(stdout);
  3542.         }
  3543.         for (int run = 1; run <= 20; run++) {
  3544.             for (int i = 0; i < n; i++)
  3545.                 made[i] = cur[i];
  3546.             t1 = clock();
  3547.             radixsort(made, made + n);
  3548.             t2 = clock();
  3549.             output = "Results\\Part sorted\\radixsort1e7.txt";
  3550.             freopen(output.c_str(), "a", stdout);
  3551.             if (!check(n)) printf("incorrect");
  3552.             else printf("%d", t2 - t1);
  3553.             if (run != 20) printf(" ");
  3554.             else printf("\n");
  3555.             fclose(stdout);
  3556.         }
  3557.         for (int run = 1; run <= 20; run++) {
  3558.             for (int i = 0; i < n; i++)
  3559.                 made[i] = cur[i];
  3560.             t1 = clock();
  3561.             timsort(made, made + n);
  3562.             t2 = clock();
  3563.             output = "Results\\Part sorted\\timsort1e7.txt";
  3564.             freopen(output.c_str(), "a", stdout);
  3565.             if (!check(n)) printf("incorrect");
  3566.             else printf("%d", t2 - t1);
  3567.             if (run != 20) printf(" ");
  3568.             else printf("\n");
  3569.             fclose(stdout);
  3570.         }
  3571.         for (int run = 1; run <= 20; run++) {
  3572.             for (int i = 0; i < n; i++)
  3573.                 made[i] = cur[i];
  3574.             t1 = clock();
  3575.             myshell1(made, made + n);
  3576.             t2 = clock();
  3577.             output = "Results\\Part sorted\\myshell1_1e7.txt";
  3578.             freopen(output.c_str(), "a", stdout);
  3579.             if (!check(n)) printf("incorrect");
  3580.             else printf("%d", t2 - t1);
  3581.             if (run != 20) printf(" ");
  3582.             else printf("\n");
  3583.             fclose(stdout);
  3584.         }
  3585.         for (int run = 1; run <= 20; run++) {
  3586.             for (int i = 0; i < n; i++)
  3587.                 made[i] = cur[i];
  3588.             t1 = clock();
  3589.             myshell2(made, made + n);
  3590.             t2 = clock();
  3591.             output = "Results\\Part sorted\\myshell2_1e7.txt";
  3592.             freopen(output.c_str(), "a", stdout);
  3593.             if (!check(n)) printf("incorrect");
  3594.             else printf("%d", t2 - t1);
  3595.             if (run != 20) printf(" ");
  3596.             else printf("\n");
  3597.             fclose(stdout);
  3598.         }
  3599.         for (int run = 1; run <= 20; run++) {
  3600.             for (int i = 0; i < n; i++)
  3601.                 made[i] = cur[i];
  3602.             t1 = clock();
  3603.             myshell3(made, made + n);
  3604.             t2 = clock();
  3605.             output = "Results\\Part sorted\\myshell3_1e7.txt";
  3606.             freopen(output.c_str(), "a", stdout);
  3607.             if (!check(n)) printf("incorrect");
  3608.             else printf("%d", t2 - t1);
  3609.             if (run != 20) printf(" ");
  3610.             else printf("\n");
  3611.             fclose(stdout);
  3612.         }
  3613.     }
  3614.     for (int t = 91; t <= 130; t++) {
  3615.         n = read("Part sorted\\test" + to_string(t) + ".txt");
  3616.         for (int run = 1; run <= 20; run++) {
  3617.             for (int i = 0; i < n; i++)
  3618.                 made[i] = cur[i];
  3619.             t1 = clock();
  3620.             combsort(made, made + n);
  3621.             t2 = clock();
  3622.             output = "Results\\Part sorted\\combsort1e8.txt";
  3623.             freopen(output.c_str(), "a", stdout);
  3624.             if (!check(n)) printf("incorrect");
  3625.             else printf("%d", t2 - t1);
  3626.             if (run != 20) printf(" ");
  3627.             else printf("\n");
  3628.             fclose(stdout);
  3629.         }
  3630.         for (int run = 1; run <= 20; run++) {
  3631.             for (int i = 0; i < n; i++)
  3632.                 made[i] = cur[i];
  3633.             t1 = clock();
  3634.             newbucketsort(made, made + n);
  3635.             t2 = clock();
  3636.             output = "Results\\Part sorted\\bucketsort1e8.txt";
  3637.             freopen(output.c_str(), "a", stdout);
  3638.             if (!check(n)) printf("incorrect");
  3639.             else printf("%d", t2 - t1);
  3640.             if (run != 20) printf(" ");
  3641.             else printf("\n");
  3642.             fclose(stdout);
  3643.         }
  3644.         for (int run = 1; run <= 20; run++) {
  3645.             for (int i = 0; i < n; i++)
  3646.                 made[i] = cur[i];
  3647.             t1 = clock();
  3648.             heapsort(made, made + n);
  3649.             t2 = clock();
  3650.             output = "Results\\Part sorted\\heapsort1e8.txt";
  3651.             freopen(output.c_str(), "a", stdout);
  3652.             if (!check(n)) printf("incorrect");
  3653.             else printf("%d", t2 - t1);
  3654.             if (run != 20) printf(" ");
  3655.             else printf("\n");
  3656.             fclose(stdout);
  3657.         }
  3658.         for (int run = 1; run <= 20; run++) {
  3659.             for (int i = 0; i < n; i++)
  3660.                 made[i] = cur[i];
  3661.             t1 = clock();
  3662.             sort(made, made + n);
  3663.             t2 = clock();
  3664.             output = "Results\\Part sorted\\stlsort1e8.txt";
  3665.             freopen(output.c_str(), "a", stdout);
  3666.             if (!check(n)) printf("incorrect");
  3667.             else printf("%d", t2 - t1);
  3668.             if (run != 20) printf(" ");
  3669.             else printf("\n");
  3670.             fclose(stdout);
  3671.         }
  3672.         for (int run = 1; run <= 20; run++) {
  3673.             for (int i = 0; i < n; i++)
  3674.                 made[i] = cur[i];
  3675.             t1 = clock();
  3676.             quicksort(made, made + n);
  3677.             t2 = clock();
  3678.             output = "Results\\Part sorted\\quicksort1e8.txt";
  3679.             freopen(output.c_str(), "a", stdout);
  3680.             if (!check(n)) printf("incorrect");
  3681.             else printf("%d", t2 - t1);
  3682.             if (run != 20) printf(" ");
  3683.             else printf("\n");
  3684.             fclose(stdout);
  3685.         }
  3686.         for (int run = 1; run <= 20; run++) {
  3687.             for (int i = 0; i < n; i++)
  3688.                 made[i] = cur[i];
  3689.             t1 = clock();
  3690.             quickinssort(made, made + n);
  3691.             t2 = clock();
  3692.             output = "Results\\Part sorted\\quickinssort1e8.txt";
  3693.             freopen(output.c_str(), "a", stdout);
  3694.             if (!check(n)) printf("incorrect");
  3695.             else printf("%d", t2 - t1);
  3696.             if (run != 20) printf(" ");
  3697.             else printf("\n");
  3698.             fclose(stdout);
  3699.         }
  3700.         for (int run = 1; run <= 20; run++) {
  3701.             for (int i = 0; i < n; i++)
  3702.                 made[i] = cur[i];
  3703.             t1 = clock();
  3704.             mergesort(made, made + n);
  3705.             t2 = clock();
  3706.             output = "Results\\Part sorted\\mergesort1e8.txt";
  3707.             freopen(output.c_str(), "a", stdout);
  3708.             if (!check(n)) printf("incorrect");
  3709.             else printf("%d", t2 - t1);
  3710.             if (run != 20) printf(" ");
  3711.             else printf("\n");
  3712.             fclose(stdout);
  3713.         }
  3714.         for (int run = 1; run <= 20; run++) {
  3715.             for (int i = 0; i < n; i++)
  3716.                 made[i] = cur[i];
  3717.             t1 = clock();
  3718.             mergeinssort(made, made + n);
  3719.             t2 = clock();
  3720.             output = "Results\\Part sorted\\mergeinssort1e8.txt";
  3721.             freopen(output.c_str(), "a", stdout);
  3722.             if (!check(n)) printf("incorrect");
  3723.             else printf("%d", t2 - t1);
  3724.             if (run != 20) printf(" ");
  3725.             else printf("\n");
  3726.             fclose(stdout);
  3727.         }
  3728.         for (int run = 1; run <= 20; run++) {
  3729.             for (int i = 0; i < n; i++)
  3730.                 made[i] = cur[i];
  3731.             t1 = clock();
  3732.             shellsort(made, made + n);
  3733.             t2 = clock();
  3734.             output = "Results\\Part sorted\\shellsort1e8.txt";
  3735.             freopen(output.c_str(), "a", stdout);
  3736.             if (!check(n)) printf("incorrect");
  3737.             else printf("%d", t2 - t1);
  3738.             if (run != 20) printf(" ");
  3739.             else printf("\n");
  3740.             fclose(stdout);
  3741.         }
  3742.         for (int run = 1; run <= 20; run++) {
  3743.             for (int i = 0; i < n; i++)
  3744.                 made[i] = cur[i];
  3745.             t1 = clock();
  3746.             shellsortsedgwick(made, made + n);
  3747.             t2 = clock();
  3748.             output = "Results\\Part sorted\\shellsortsedgwick1e8.txt";
  3749.             freopen(output.c_str(), "a", stdout);
  3750.             if (!check(n)) printf("incorrect");
  3751.             else printf("%d", t2 - t1);
  3752.             if (run != 20) printf(" ");
  3753.             else printf("\n");
  3754.             fclose(stdout);
  3755.         }
  3756.         for (int run = 1; run <= 20; run++) {
  3757.             for (int i = 0; i < n; i++)
  3758.                 made[i] = cur[i];
  3759.             t1 = clock();
  3760.             radixsort(made, made + n);
  3761.             t2 = clock();
  3762.             output = "Results\\Part sorted\\radixsort1e8.txt";
  3763.             freopen(output.c_str(), "a", stdout);
  3764.             if (!check(n)) printf("incorrect");
  3765.             else printf("%d", t2 - t1);
  3766.             if (run != 20) printf(" ");
  3767.             else printf("\n");
  3768.             fclose(stdout);
  3769.         }
  3770.         for (int run = 1; run <= 20; run++) {
  3771.             for (int i = 0; i < n; i++)
  3772.                 made[i] = cur[i];
  3773.             t1 = clock();
  3774.             timsort(made, made + n);
  3775.             t2 = clock();
  3776.             output = "Results\\Part sorted\\timsort1e8.txt";
  3777.             freopen(output.c_str(), "a", stdout);
  3778.             if (!check(n)) printf("incorrect");
  3779.             else printf("%d", t2 - t1);
  3780.             if (run != 20) printf(" ");
  3781.             else printf("\n");
  3782.             fclose(stdout);
  3783.         }
  3784.         for (int run = 1; run <= 20; run++) {
  3785.             for (int i = 0; i < n; i++)
  3786.                 made[i] = cur[i];
  3787.             t1 = clock();
  3788.             myshell1(made, made + n);
  3789.             t2 = clock();
  3790.             output = "Results\\Part sorted\\myshell1_1e8.txt";
  3791.             freopen(output.c_str(), "a", stdout);
  3792.             if (!check(n)) printf("incorrect");
  3793.             else printf("%d", t2 - t1);
  3794.             if (run != 20) printf(" ");
  3795.             else printf("\n");
  3796.             fclose(stdout);
  3797.         }
  3798.         for (int run = 1; run <= 20; run++) {
  3799.             for (int i = 0; i < n; i++)
  3800.                 made[i] = cur[i];
  3801.             t1 = clock();
  3802.             myshell2(made, made + n);
  3803.             t2 = clock();
  3804.             output = "Results\\Part sorted\\myshell2_1e8.txt";
  3805.             freopen(output.c_str(), "a", stdout);
  3806.             if (!check(n)) printf("incorrect");
  3807.             else printf("%d", t2 - t1);
  3808.             if (run != 20) printf(" ");
  3809.             else printf("\n");
  3810.             fclose(stdout);
  3811.         }
  3812.         for (int run = 1; run <= 20; run++) {
  3813.             for (int i = 0; i < n; i++)
  3814.                 made[i] = cur[i];
  3815.             t1 = clock();
  3816.             myshell3(made, made + n);
  3817.             t2 = clock();
  3818.             output = "Results\\Part sorted\\myshell3_1e8.txt";
  3819.             freopen(output.c_str(), "a", stdout);
  3820.             if (!check(n)) printf("incorrect");
  3821.             else printf("%d", t2