1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
void print(int a[], int n)
{
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
cout << endl;
}
// QuickSort
int partition(int *a, int st, int ed)
{
int pivot = a[ed];
int pIndex = st;
for (int i = st; i < ed; i++)
{
if (a[i] <= pivot)
{
int temp = a[i];
a[i] = a[pIndex];
a[pIndex] = temp;
pIndex++;
}
}
int temp = a[pIndex];
a[pIndex] = a[ed];
a[ed] = temp;
return pIndex;
}
void QuickSort(int *a, int start, int end)
{
if (start >= end)
{
return;
}
int index = partition(a, start, end);
QuickSort(a, start, index - 1);
QuickSort(a, index + 1, end);
}
signed main(){
int n;
cin >> n;
int a[n];
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
Quick(a, n);
print(a, n);
return 0;
}Like Merge Sort, QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.