-
Notifications
You must be signed in to change notification settings - Fork 51
Expand file tree
/
Copy pathQuickSort.cpp
More file actions
56 lines (50 loc) · 1.54 KB
/
Copy pathQuickSort.cpp
File metadata and controls
56 lines (50 loc) · 1.54 KB
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
54
55
56
// O(nlog(n)) --> average time Complexcity
// O(n^2) --> worst case (If 1st element is chosen as pivot and arr is sorted)
// O(1) --> Extra Space
// Link --> https://www.hackerearth.com/practice/algorithms/sorting/quick-sort/tutorial/
// Link --> https://www.youtube.com/watch?v=if40LxQ8_Xo&t=1171s
#include<bits/stdc++.h>
using namespace std;
// All ements to the left of pivot are less than pivot and to the right are greater
// It means the element is in its sorted position
int partition(vector<int> &arr, int lo, int hi){
int j,i = lo+1;
int pivot = arr[lo]; // We try to find index of pivot
/*
arr[lo] is our pivot
Our array lo to hi is divided into 3 regions:
[lo+1,j-1] --> Less than Pivot
[j,i-1] --> More than Pivot
[i,hi] --> Unchecked
*/
for(j=lo+1;j<=hi;j++){
if(arr[j] < pivot){
swap(arr[i],arr[j]);
i++;
}
}
// i-1 is largest index with no. less than pivot
// So it is pivot index
swap(arr[lo],arr[i-1]);
return i-1;
}
// Divide and Conquer Algo
void quickSort(vector<int> &arr, int lo, int hi){
if(lo>=hi)
return;
int pivot_index = partition(arr,lo,hi);
quickSort(arr,lo,pivot_index-1);
quickSort(arr,pivot_index+1,hi);
}
void print(vector<int> arr){
cout << "Sorted Array is : ";
for(int i=0;i<arr.size();i++)
cout << arr[i] <<" ";
cout << endl;
}
int main(){
int n = 10;
vector<int> arr = {3,6,1,2,10,7,8,5,9,0};
quickSort(arr,0,n-1);
print(arr);
}