-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathmain.cpp
More file actions
66 lines (51 loc) · 1.38 KB
/
Copy pathmain.cpp
File metadata and controls
66 lines (51 loc) · 1.38 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
57
58
59
60
61
62
63
64
65
66
#include <iostream>
using namespace std;
int ARR[10] = { 42,89,63,12,94,27,78,3,50,36 };
//int ARR[10] = { 3, 12, 27, 36, 42, 50, 63, 78, 89, 94 };
int COUNT = 0;
void Swap(int* const arr, const int a_index, const int b_index) {
if (a_index == b_index) {
return;
}
arr[a_index] = arr[a_index] ^ arr[b_index];
arr[b_index] = arr[a_index] ^ arr[b_index];
arr[a_index] = arr[a_index] ^ arr[b_index];
}
int Partition(int* const arr, const int left, const int right) {
cout << "[" << COUNT << "] call Partition(" << left << "," << right << ")" << endl;
int i = left - 1;
int j = left;
int m = (left + right) >> 1;
int p = arr[m];
while (j < right) {
if (arr[j] < p) {
i++;
Swap(arr, i, j);
}
j++;
}
Swap(arr, i + 1, j);
return i + 1;
}
void QuickSort(int* const arr, const int left, const int right) {
cout << "[" << ++COUNT << "] call QuickSort(" << left << "," << right << ")" << endl;
if (left >= right) {
return;
}
int p = Partition(arr, left, right);
cout << " QuickSort(" << left << "," << right << ") Pivot = " << p << endl;
QuickSort(arr, left, p - 1);
QuickSort(arr, p + 1, right);
}
void PrintArray(int* const arr, const int length) {
for (int i = 0; i < length; i++) {
cout << arr[i] << ' ';
}
cout << endl;
}
int main() {
const int length = sizeof(ARR) / sizeof(ARR[0]);
QuickSort(ARR, 0, length - 1);
PrintArray(ARR, length);
return 0;
}