inhuman_Arif

Quicksort

Oct 20th, 2021
651
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. typedef long long ll;
  5. int partition(int arr[],int left,int right)
  6. {
  7.     int x = arr[right]; //initialize comparing value
  8.     int i = left-1;
  9.     //exchanging elements if necessary or exchange with themselves
  10.     for(int j=left;j<=right-1;j++)
  11.     {
  12.         if(arr[j]<x)
  13.         {
  14.             i++;
  15.             swap(arr[i],arr[j]);
  16.         }
  17.     }
  18.     //exchange with compared value to put it on the right place
  19.     swap(arr[i+1],arr[right]);
  20.     return i+1; //return the index
  21. }
  22.  
  23. void quicksort(int arr[],int left,int right)
  24. {
  25.     //base case
  26.     if(left>=right)
  27.         return;
  28.     //process
  29.     int q = partition(arr,left,right); //partitioning index
  30.     //recursive call
  31.     quicksort(arr,left,q-1);
  32.     quicksort(arr,q+1,right);
  33. }
  34.  
  35. int main()
  36. {
  37.     #ifndef ONLINE_JUDGE
  38.         freopen("input.txt", "r", stdin);
  39.         freopen("output.txt", "w", stdout);
  40.     #endif
  41.  
  42.     int n;
  43.     cin >> n; //declaring array size
  44.     int arr[n]; //declaring array
  45.     for(int i=0;i<n;i++)
  46.         cin >> arr[i];
  47.     //calling function
  48.     quicksort(arr,0,n-1);
  49.     //printing array
  50.     for(int i=0;i<n;i++)
  51.         cout << arr[i] << ' ';
  52.    
  53.     return 0;
  54. }
RAW Paste Data