OR-Tools  8.2
sort.h
Go to the documentation of this file.
1 // Copyright 2010-2018 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
14 #ifndef OR_TOOLS_UTIL_SORT_H_
15 #define OR_TOOLS_UTIL_SORT_H_
16 
17 #include <algorithm>
18 #include <functional>
19 #include <iterator>
20 
21 namespace operations_research {
22 
23 template <class Iterator>
24 using value_type_t = typename std::iterator_traits<Iterator>::value_type;
25 
26 // Sorts the elements in the range [begin, end) in ascending order using the
27 // comp predicate. The order of equal elements is guaranteed to be preserved
28 // only if is_stable is true.
29 //
30 // This function performs well if the elements in the range [begin, end) are
31 // almost sorted.
32 //
33 // The algorithm operates as follows:
34 // 1) Check that the range [begin, end) is already sorted by performing a
35 // single iteration of bubble-sort.
36 // 2) Try to sort the range with insertion sort. Insertion sort will stop if it
37 // uses the comp predicate more than max_comparisons. Note that the algorithm
38 // may actually use the comp predicate more than max_comparisons in order
39 // to complete its current insertion.
40 // 3) If insertion sort exceeds the maximum number of comparisons, the range is
41 // sorted using std::stable_sort if is_stable is true or std::sort otherwise.
42 //
43 // The first two steps of this algorithm are inspired by the ones recommended
44 // in Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
45 template <class Iterator, class Compare = std::less<value_type_t<Iterator>>>
46 void IncrementalSort(int max_comparisons, Iterator begin, Iterator end,
47  Compare comp = Compare{}, bool is_stable = false) {
48  // Ranges of at most one element are already sorted.
49  if (std::distance(begin, end) <= 1) return;
50 
51  // Perform a single iteration of bubble-sort to place the smallest unsorted
52  // element to its correct position.
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));
57  last_sorted = it;
58  }
59  }
60 
61  // We know that the elements in the range [begin, last_sorted) are the
62  // smallest elements of [begin, end) and are sorted.
63  Iterator it = std::next(last_sorted);
64  for (; it != end && max_comparisons > 0; ++it) {
65  const auto inserted = *it;
66  Iterator j = it;
67  max_comparisons--;
68  while (comp(inserted, *std::prev(j))) {
69  max_comparisons--;
70  *j = *std::prev(j);
71  j--;
72  }
73  *j = inserted;
74  }
75 
76  // Stop if insertion sort was able to sort the range.
77  if (it == end) return;
78 
79  if (is_stable) {
80  std::stable_sort(last_sorted, end, comp);
81  } else {
82  std::sort(last_sorted, end, comp);
83  }
84 }
85 
86 // Sorts the elements in the range [begin, end) in ascending order using the
87 // comp predicate. The order of equal elements is guaranteed to be preserved.
88 //
89 // This function performs well if the elements in the range [begin, end) are
90 // almost sorted.
91 //
92 // This algorithm is inspired by the ones recommended in Algorithms, 4th Edition
93 // by Robert Sedgewick and Kevin Wayne.
94 template <class Iterator, class Compare = std::less<value_type_t<Iterator>>>
95 void InsertionSort(Iterator begin, Iterator end, Compare comp = Compare{}) {
96  // Ranges of at most one element are already sorted.
97  if (std::distance(begin, end) <= 1) return;
98 
99  // Perform a single iteration of bubble-sort to place the smallest unsorted
100  // element to its correct position.
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));
105  last_sorted = it;
106  }
107  }
108 
109  // We know that the elements in the range [begin, last_sorted) are the
110  // smallest elements of [begin, end) and are sorted.
111  for (Iterator it = std::next(last_sorted); it != end; ++it) {
112  const auto inserted = *it;
113  Iterator j = it;
114  while (comp(inserted, *std::prev(j))) {
115  *j = *std::prev(j);
116  j--;
117  }
118  *j = inserted;
119  }
120 }
121 
122 // Sorts the elements in the range [begin, end) in ascending order using the
123 // comp predicate. The order of equal elements is guaranteed to be preserved
124 // only if is_stable is true.
125 //
126 // This function performs well if the elements in the range [begin, end) are
127 // almost sorted.
128 template <class Iterator, class Compare = std::less<value_type_t<Iterator>>>
129 void IncrementalSort(Iterator begin, Iterator end, Compare comp = Compare{},
130  bool is_stable = false) {
131  const int size = std::distance(begin, end);
132  if (size <= 32) {
133  InsertionSort(begin, end, comp);
134  } else {
135  IncrementalSort(size * 8, begin, end, comp, is_stable);
136  }
137 }
138 
139 } // namespace operations_research
140 
141 #endif // OR_TOOLS_UTIL_SORT_H_
Block * next
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)
Definition: sort.h:46
typename std::iterator_traits< Iterator >::value_type value_type_t
Definition: sort.h:24
void InsertionSort(Iterator begin, Iterator end, Compare comp=Compare{})
Definition: sort.h:95