14 #ifndef OR_TOOLS_UTIL_SORT_H_
15 #define OR_TOOLS_UTIL_SORT_H_
23 template <
class Iterator>
24 using value_type_t =
typename std::iterator_traits<Iterator>::value_type;
45 template <
class Iterator,
class Compare = std::less<value_type_t<Iterator>>>
47 Compare comp = Compare{},
bool is_stable =
false) {
49 if (std::distance(begin, end) <= 1)
return;
53 Iterator last_sorted = std::prev(end);
54 for (
auto it = last_sorted; it != begin; --it) {
55 if (comp(*it, *std::prev(it))) {
56 std::iter_swap(it, std::prev(it));
64 for (; it != end && max_comparisons > 0; ++it) {
65 const auto inserted = *it;
68 while (comp(inserted, *std::prev(j))) {
77 if (it == end)
return;
80 std::stable_sort(last_sorted, end, comp);
82 std::sort(last_sorted, end, comp);
94 template <
class Iterator,
class Compare = std::less<value_type_t<Iterator>>>
95 void InsertionSort(Iterator begin, Iterator end, Compare comp = Compare{}) {
97 if (std::distance(begin, end) <= 1)
return;
101 Iterator last_sorted = std::prev(end);
102 for (
auto it = last_sorted; it != begin; --it) {
103 if (comp(*it, *std::prev(it))) {
104 std::iter_swap(it, std::prev(it));
111 for (Iterator it =
std::next(last_sorted); it != end; ++it) {
112 const auto inserted = *it;
114 while (comp(inserted, *std::prev(j))) {
128 template <
class Iterator,
class Compare = std::less<value_type_t<Iterator>>>
130 bool is_stable =
false) {
131 const int size = std::distance(begin, end);
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
void IncrementalSort(int max_comparisons, Iterator begin, Iterator end, Compare comp=Compare{}, bool is_stable=false)
typename std::iterator_traits< Iterator >::value_type value_type_t
void InsertionSort(Iterator begin, Iterator end, Compare comp=Compare{})