-
Notifications
You must be signed in to change notification settings - Fork 38
/
quick_sort.cpp
35 lines (30 loc) · 876 Bytes
/
quick_sort.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
#include <vector>
template <class T> void _quick_sort(std::vector<T> &arr, int start, int end) {
while (end > start) {
int i = start;
int j = end;
while (i < j) {
while (arr[i] < arr[start] && i < j)
i++;
while (arr[--j] > arr[start])
;
if (i < j)
std::swap(arr[i], arr[j]);
}
std::swap(arr[start], arr[j]);
if (j - start > end - (j + 1)) {
_quick_sort(arr, start, j - 1);
start = j + 1;
} else {
_quick_sort(arr, j + 1, end);
end = j - 1;
}
}
}
template <class T> void quick_sort(std::vector<T> &arr) {
_quick_sort(arr, 0, arr.size());
}
template void quick_sort<int>(std::vector<int> &arr);
template void quick_sort<float>(std::vector<float> &arr);
template void quick_sort<double>(std::vector<double> &arr);
template void quick_sort<char>(std::vector<char> &arr);