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
|
#pragma once
namespace AK {
template<typename IteratorType, typename LessThan>
IteratorType partition(IteratorType first, IteratorType last, LessThan less_than)
{
auto pivot = last;
auto smallest = first - 1;
auto it = first;
for (; it < last; ++it) {
if (less_than(*it, *pivot)) {
++smallest;
swap(*it, *smallest);
}
}
swap(*(smallest + 1), *last);
return smallest + 1;
}
template<typename IteratorType, typename LessThan>
void quick_sort_impl(IteratorType begin, IteratorType first, IteratorType last, LessThan less_than)
{
if (first < last) {
auto pivot = partition(first, last, less_than);
quick_sort_impl(begin, first, pivot - 1, less_than);
quick_sort_impl(begin, pivot + 1, last, less_than);
}
}
template<typename T>
bool is_less_than(const T& a, const T& b)
{
return a < b;
}
template<typename IteratorType, typename LessThan>
void quick_sort(IteratorType begin, IteratorType end, LessThan less_than = is_less_than)
{
if (begin == end)
return;
quick_sort_impl(begin, begin, end - 1, less_than);
}
}
using AK::quick_sort;
|
