# 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