allia

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

Oct 18th, 2020
708
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include<cstdlib>
  5.  
  6. using namespace std;
  7.  
  8.  
  9. void quick_sort (int *A, int first, int last)
  10. {
  11. int x, i, j, c = first, d = last;
  12.  
  13. while (c < d)
  14. {
  15.   int m = (c+d)/2;
  16.  
  17.  if (A[c] > A[d] && A[c] < A[m])
  18.  x = A[c];
  19.   else if (A[d] > A[c] && A[d] < A[m])
  20.    x = A[d];
  21.     else x = A[m];
  22.  
  23.  i = c;
  24.  j = d;
  25.    
  26.    while (i < j)
  27.    {
  28.     while (A[i] < x)
  29.      i++;
  30.     while (A[j] > x)
  31.      j--;
  32.  
  33.     if (i <= j)
  34.      {
  35.        swap(A[i], A[j]);
  36.        i++;
  37.        j--;
  38.      }
  39.    }
  40.  
  41. if (j-c < d-i)
  42.  {
  43.    if (c < j)
  44.     quick_sort(A,c,j);
  45.     c = i;
  46.  }
  47. else
  48.  {
  49.    if (i<d)
  50.    quick_sort(A,i,d);
  51.    d = j;
  52.  }
  53. }
  54. }
  55.  
  56. int main ()
  57. {
  58.   int n;
  59.   cin >> n;
  60.   int *arr = new int[n];
  61.  
  62.   for (int i=0; i<n; i++)
  63.   cin >> arr[i];
  64.  
  65.   quick_sort(arr, 0, n-1);
  66.  
  67.   for (int i=0; i<n; i++)
  68.   cout << arr[i] << " ";
  69. }
RAW Paste Data