farhin_khaled

Quick Sort

Oct 20th, 2021 (edited)
659
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define ll long long int
  3. #define ull unsigned long long int
  4. #define pb push_back
  5. #define mp make_pair
  6. #define in insert
  7. #define f first
  8. #define sc second
  9. #define M 1000000
  10. #define MAX 1000010
  11. using namespace std;
  12.  
  13. int partition(int a[],int lb,int ub)
  14. {
  15.   int start = lb;
  16.   int end = ub;
  17.   int pivot = a[lb];
  18.   while(start<end)
  19.   {
  20.     while(a[start]<=pivot) start++;
  21.     while(a[end]>pivot) end--;
  22.     if(start<end) swap(a[start],a[end]);
  23.   }
  24.   swap(a[lb],a[end]);
  25.   return end;
  26. }
  27.  
  28. void quicksort(int a[],int lb,int ub)
  29. {
  30.   if(lb<ub)
  31.   {
  32.     int loc = partition(a,lb,ub);
  33.     quicksort(a,lb,loc-1);
  34.     quicksort(a,loc+1,ub);
  35.   }
  36. }
  37.  
  38. void printArray(int a[],int n)
  39. {
  40.   for(int i=0;i<n;i++) cout << a[i] << " ";
  41. }
  42.  
  43. int main()
  44. {
  45.   int n;
  46.   cin >> n;
  47.   int a[n];
  48.   for(int i=0;i<n;i++) cin >> a[i];
  49.   cout << "Before sorting:" << endl;
  50.   printArray(a,n);
  51.   cout << endl << endl;
  52.   quicksort(a,0,n-1);
  53.   cout << "After sorting:" << endl;
  54.   printArray(a,n);
  55.  
  56.   return 0;
  57. }
  58.  
RAW Paste Data