# 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