SHARE
TWEET

Untitled

a guest Jan 22nd, 2020 79 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. void swap(int* a, int* b)
  6. {
  7.     int t = *a;
  8.     *a = *b;
  9.     *b = t;
  10. }
  11.  
  12. int part_sort(int arr[], int l, int r)
  13. {
  14.     int pivot = arr[l];
  15.     int i = r + 1;
  16.     for (int j = r; j > l; j--)
  17.         if (arr[j] >= pivot)
  18.         {
  19.             i--;
  20.             swap(&arr[i], &arr[j]);
  21.         }
  22.     swap(&arr[i - 1], &arr[l]);
  23.     return(i - 1);
  24. }
  25.  
  26.  
  27. void quick_sort(int arr[], int l, int r)
  28. {
  29.     int st_arr[r - l + 1];
  30.     int top = -1;
  31.     st_arr[++top] = l;
  32.     st_arr[++top] = r;
  33.     while (top >= 0)
  34.     {
  35.         r = st_arr[top--];
  36.         l = st_arr[top--];
  37.         int p = part_sort(arr, l, r);
  38.         if (l < p - 1)
  39.         {
  40.             st_arr[++top] = l;
  41.             st_arr[++top] = p - 1;
  42.         }
  43.         if (p + 1 < r)
  44.         {
  45.             st_arr[++top] = p + 1;
  46.             st_arr[++top] = r;
  47.         }
  48.     }
  49. }
  50.  
  51. int main()
  52. {
  53.     setlocale(LC_ALL, "Russian");
  54.     cout << "Введите длину массива: ";
  55.     int n;
  56.     cin >> n;
  57.     int *arr = new int[n];
  58.  
  59.     cout << "Введите 1, если хотите вручную ввести значения," << endl;
  60.     cout << "или любое другое число, если хотите срандомить: " << endl;
  61.  
  62.     int check;
  63.     cin >> check;
  64.  
  65.     cout << endl;
  66.     cout << "Исходный массив: " << endl;
  67.  
  68.     if (check == 1)
  69.         for (int i = 0; i < n; i++)
  70.             cin >> arr[i];
  71.     else
  72.     {
  73.         for (int i = 0; i < n; i++)
  74.         {
  75.             arr[i] = rand() % n + 1;
  76.             cout << arr[i] << " ";
  77.         }
  78.         cout << endl;
  79.     }
  80.     quick_sort(arr, 0, n - 1);
  81.     cout << endl;
  82.     cout << "Массив после сортировки: " << endl;
  83.     for (int i = 0; i < n; i++)
  84.         cout << arr[i] << " ";
  85.     return 0;
  86. }
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
Top