Guest User

Untitled

a guest
Dec 2nd, 2019
104
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