SHARE
TWEET

Untitled

a guest Dec 2nd, 2019 97 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // 1) Выберем опорный X (как именно - ?)
  2. // 2) Тернарное разбрасывание в идеале или бинарное
  3. // 3) рекурсивно запускается от "<X" и ">X"
  4. // 4) Худший случай: в качестве опорного элемента всегда берём max или min O(n^2)
  5. // 5) Лучший случай: константный случай W(n)
  6.  
  7. #include <iostream>
  8. using namespace std;
  9.  
  10. int cnt = 0;
  11. const int size = 10000;
  12.  
  13. void qsort(int * l, int * r) {
  14.     ++cnt;
  15.     if (r - l <= 1) return;
  16.     int x = rand() % (r - l);
  17.     int left[size], middle[size], right[size];
  18.     int le = 0, mi = 0, ri = 0;
  19.     cnt += 4;
  20.     for (int i = 0; i < r - l; ++i) {
  21.         cnt += 3;
  22.         if (*(l + i) == *(l + x)) {
  23.             middle[mi++] = *(l + i);
  24.         } else if (*(l + i) < *(l + x)) {
  25.             left[le++] = *(l + i);
  26.         } else {
  27.             right[ri++] = *(l + i);
  28.         }
  29.     }
  30.     cnt++;
  31.     middle[mi++] = *(l + x);
  32.     qsort(left, left + le);
  33.     qsort(right, right + ri);
  34.     for (int i = 0; i < le; ++i) {
  35.         cnt++;
  36.         *(l++) = left[i];
  37.     }
  38.     for (int i = 0; i < mi; ++i) {
  39.         cnt++;
  40.         *(l++) = middle[i];
  41.     }
  42.     for (int i = 0; i < ri; ++i) {
  43.         cnt++;
  44.         *(l++) = right[i];
  45.     }
  46. }
  47.  
  48. int main() {
  49.     srand(0);
  50.     int arr[size];
  51.     int n;
  52.     cin >> n;
  53.     for (int k = 0; k < 7; ++k) {
  54.         cnt = 0;
  55.         for (int i = 0; i < n; ++i) {
  56.             arr[i] = rand() % 10000;
  57.         }
  58.         qsort(arr, arr + n);    
  59.         cout << cnt << endl;
  60.     }
  61.     return 0;
  62. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top