wrench786

Lab Task - Quick Sort

Oct 20th, 2021
669
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define ull unsigned long long
  5. #define uom unordered_map
  6. #define pb push_back
  7. #define yes cout<<"Yes\n"
  8. #define no cout<<"No\n"
  9.  
  10. #define dot(x) fixed<<setprecision(x)
  11. #define wrench786 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  12.  
  13. #define PI (acos(-1.0))
  14. #define eps 0.00001
  15. const int LIMIT = 10000*20;
  16. const int mod = 1000000007;
  17. using namespace std;
  18.  
  19.  
  20. int partition (int arr[], int low, int high)
  21. {
  22.     int x = arr[high];
  23.     int i = (low - 1);
  24.  
  25.     for (int j = low; j <= high - 1; j++)
  26.     {
  27.         if (arr[j] < x)
  28.         {
  29.             i++;
  30.             swap(arr[i], arr[j]);
  31.         }
  32.     }
  33.     swap(arr[i + 1], arr[high]);
  34.     return (i + 1);
  35. }
  36.  
  37. void quickSort(int arr[], int low, int high)
  38. {
  39.     if (low < high)
  40.     {
  41.         int pi = partition(arr, low, high);
  42.         quickSort(arr, low, pi - 1);
  43.         quickSort(arr, pi + 1, high);
  44.     }
  45. }
  46.  
  47. int main()
  48. {
  49.     int n;
  50.     cin>>n;
  51.     int arr[n];
  52.     for(int i=0;i<n;i++){
  53.         cin>>arr[i];
  54.     }
  55.     quickSort(arr, 0, n - 1);
  56.    
  57.     for (int i = 0; i < n; i++){
  58.         cout << arr[i] << " ";
  59.     }
  60.     cout << endl;
  61. }
RAW Paste Data