-
Notifications
You must be signed in to change notification settings - Fork 4
/
Copy pathQuickSort.cpp
41 lines (41 loc) · 1.24 KB
/
QuickSort.cpp
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
#include <iostream>
#include <cmath>
using namespace std;
int Partition(int LowerBound, int UpperBound, int Array[]){
int Pivot = Array[UpperBound];
int SmallerElementIndex = LowerBound;
for(int i = LowerBound;i<UpperBound;i++){
if(Array[i]<Pivot){
int temp = Array[LowerBound];
Array[LowerBound] = Array[i];
Array[i] = temp;
SmallerElementIndex++;
}
}
Array[UpperBound] = Array[SmallerElementIndex];
Array[SmallerElementIndex] = Pivot;
return SmallerElementIndex;
}
void QuickSort(int LowerBound, int UpperBound, int Array[]){
if(LowerBound>UpperBound) return;
if(LowerBound==UpperBound) return;
if(UpperBound==(LowerBound+1)){
int Smaller = min(Array[LowerBound], Array[UpperBound]);
int Larger = max(Array[LowerBound], Array[UpperBound]);
Array[LowerBound] = Smaller;
Array[UpperBound] = Larger;
return;
}
int MidPoint = Partition(LowerBound, UpperBound, Array);
QuickSort(LowerBound, MidPoint-1, Array);
QuickSort(MidPoint + 1, UpperBound, Array);
}
int main(){
int Size;
cin>>Size;
int Array[Size];
for(int i =0 ;i<Size;i++){
cin>>Array[i];
}
QuickSort(0, Size-1, Array);
}