Advertisement
uzimane_

быстрая сортировка

Jul 10th, 2020
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.85 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <cmath>
  4.  
  5. using namespace std;
  6.  
  7. int* mas;
  8.  
  9. void qs(int* mas, int l, int r)
  10. {
  11. double x;
  12. int i, j, c = l, d = r, q;
  13. while (c < d)
  14. {
  15. x = (mas[c] + mas[d]) / 2;
  16. i = c;
  17. j = d;
  18. while (i < j)
  19. {
  20. while (mas[i] < x)
  21. i++;
  22. while (mas[j] > x)
  23. j--;
  24. if (i <= j)
  25. {
  26. swap(mas[i], mas[j]);
  27. i++;
  28. j--;
  29. }
  30. }
  31. if (j - c < d - i)
  32. {
  33. if (c < j)
  34. qs(mas, c, j);
  35. c = i;
  36. }
  37. else
  38. {
  39. if (i < d)
  40. qs(mas, i, d);
  41. d = j;
  42. }
  43. }
  44. }
  45.  
  46. int main()
  47. {
  48.  
  49. freopen("input.txt", "r", stdin);
  50. freopen("output.txt", "w", stdout);
  51.  
  52. int n;
  53. cin >> n;
  54. mas = new int[n];
  55. for (int i = 0; i < n; i++)
  56. {
  57. cin >> mas[i];
  58. }
  59. int l = 0;
  60. int r = n - 1;
  61.  
  62. qs(mas, l, r);
  63.  
  64. for (int i = 0; i < n; i++)
  65. {
  66. cout << mas[i] << " ";
  67. }
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement