-
Notifications
You must be signed in to change notification settings - Fork 0
/
QuickSort.cpp
44 lines (43 loc) · 1.02 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
42
43
44
#include <stack>
using namespace std;
int partition(int *a, int left, int right) {
if (a == nullptr || left < 0 || right <= 0||left>=right)
return -1;
int pivot = a[left];
int i = left, j = right;
while (i < j)
{
while (i > j&&a[j] >= pivot)
j--;
if(i<j)
a[i]=a[j];
while (i < j&&a[i] <= pivot)
i++;
if(i<j)
a[j]=a[i];
}
a[i] = pivot;
return i;
}
void QuickSort(int *a, int left,int right) {
if (a == nullptr || left < 0 || right <= 0 || left>right) return;
stack<int>temp;
int i, j;
temp.push(right);
temp.push(left);
while (!temp.empty()) {
i = temp.top(); temp.pop();
j = temp.top(); temp.pop();
if (i < j) {
int k = partition(a, i, j);
if (k > i) {
temp.push(k - 1);
temp.push(i);
}
if (j > k) {
temp.push(j);
temp.push(k + 1);
}
}
}
}