4 * Copyright 2003 Max-Planck-Institut fuer Informatik
8 //======================================================================
9 // A collection of flexible, generic, STL-like algorithm components
10 // for comparison-based distribution (i.e., quicksort-like) sorting.
11 //======================================================================
20 #include <cstdlib> // for rand()
22 //======================================================================
23 // Most of the algorithms here have three versions. For example a sort
24 // function can have the following forms:
26 // sort(beg, end, less);
27 // sort(beg, end, less, key);
28 // The first two forms are standard STL. The third form adds an
29 // argument key, which is a unary function. Where the second
30 // form would compare two iterators i and j as less(*i, *j),
31 // the third form does less(key(i), key(j)) instead. This allows
32 // moving some of the computation related to the comparison from
33 // less() into key(). When the same iterator is used in many
34 // comparisons (for example the pivot), key() needs to be evaluated
37 // For example, to sort objects of type T with a member function
38 // size() returning int into increasing order of size() do
39 // (TODO: test/expand this, use vector of vectors)
41 // sort(beg, end, std::less<unsigned>(), std::mem_fun(&T::size));
43 // key() may return a pointer or reference to (a member of) the object.
44 // All the algorithms assume that the value returned by key() stays
45 // valid only as long as the object is not moved.
49 // template <typename Iterator, typename Compare, typename KeyAccess>
50 // void sort(Iterator, Iterator, Compare, KeyAccess);
51 // * KeyAccess is a model of Adaptable Unary Function
52 // * Iterator is convertible to KeyAccess::argument_type
53 // * KeyAccess::result_type is convertible to the argument type
55 //======================================================================
57 //----------------------------------------------------------------------
58 // functor copy_dereference
59 // functor const_dereference
61 // Default functors to be used as key().
62 // (TODO: which one should be used as the default?)
63 // (TODO: is const_dereference::result_type a problem?)
64 //----------------------------------------------------------------------
65 template <typename Iterator>
66 class const_dereference
67 : public std::unary_function<Iterator,
68 const typename std::iterator_traits<Iterator>::value_type &>
71 const typename std::iterator_traits<Iterator>::value_type &
72 operator() (Iterator i) const { return *i; }
75 template <typename Iterator>
76 class copy_dereference
77 : public std::unary_function<Iterator,
78 typename std::iterator_traits<Iterator>::value_type>
81 typename std::iterator_traits<Iterator>::value_type
82 operator() (Iterator i) const { return *i; }
85 template <typename Iterator>
86 class default_key : public copy_dereference<Iterator> {};
90 //======================================================================
94 // (TODO: non-randomized pivot selectors)
95 //======================================================================
97 //----------------------------------------------------------------------
98 // function iter_median3
101 //----------------------------------------------------------------------
102 template <typename Iterator, typename Compare, typename KeyAccess>
104 iter_median3(Iterator a, Iterator b, Iterator c,
105 Compare less, KeyAccess key) {
106 typedef typename KeyAccess::result_type key_type;
107 key_type ka = key(a), kb = key(b), kc = key(c);
109 if (less(kb, kc)) return b;
110 else if (less(ka, kc)) return c;
112 else if (less(ka, kc)) return a;
113 else if (less(kb, kc)) return c;
116 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
118 template <typename Iterator, typename Compare>
120 iter_median3(Iterator a, Iterator b, Iterator c, Compare less) {
121 return iter_median3(a, b, c, less, default_key<Iterator>());
124 template <typename Iterator>
126 iter_median3(Iterator a, Iterator b, Iterator c) {
127 typedef typename std::iterator_traits<Iterator>::value_type key_type;
128 return iter_median3(a, b, c, std::less<key_type>(),
129 default_key<Iterator>());
133 //----------------------------------------------------------------------
134 // function random_pivot
136 // Choose pivot of as a median of three random elements
137 // (or as a single random element for small ranges)
139 // (TODO: better/faster random number generation?)
140 //----------------------------------------------------------------------
141 template <typename RandomAccessIterator, typename Compare,
144 random_pivot (RandomAccessIterator beg, RandomAccessIterator end,
145 Compare less, KeyAccess key)
147 static double scale_to_one = 1.0L/(RAND_MAX+1.0);
149 typedef typename std::iterator_traits<RandomAccessIterator>::difference_type
151 difference_type size = std::distance(beg, end);
152 double scale_to_size = size * scale_to_one;
153 RandomAccessIterator pivot;
154 pivot = beg + static_cast<difference_type>(scale_to_size*std::rand());
156 RandomAccessIterator pivot2, pivot3;
157 pivot2 = beg + static_cast<difference_type>(scale_to_size*std::rand());
158 pivot3 = beg + static_cast<difference_type>(scale_to_size*std::rand());
159 pivot = iter_median3(pivot, pivot2, pivot3, less, key);
163 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
165 template <typename RandomAccessIterator, typename Compare>
167 random_pivot(RandomAccessIterator beg, RandomAccessIterator end,
170 return random_pivot(beg, end, less,
171 default_key<RandomAccessIterator>());
174 template <typename RandomAccessIterator>
176 random_pivot(RandomAccessIterator beg, RandomAccessIterator end)
178 typedef typename std::iterator_traits<RandomAccessIterator>::value_type
180 return random_pivot(beg, end, std::less<key_type>(),
181 default_key<RandomAccessIterator>());
187 //======================================================================
189 //======================================================================
191 //----------------------------------------------------------------------
192 // function binary_partition
194 // Partitions the input range [beg,end) into two parts [beg,mid) and
195 // [mid,end) with all elements smaller than pivot in [beg, mid) and
196 // all elements larger than pivot in [mid,end). Equal elements may
197 // be in either subrange. Returns mid.
198 // PRECONDITION: pivot is in the range [beg,end)
199 //----------------------------------------------------------------------
200 template <typename RandomAccessIterator, typename Compare,
203 binary_partition(RandomAccessIterator beg, RandomAccessIterator end,
204 RandomAccessIterator pivot, Compare less, KeyAccess key)
206 if (beg == --end) return beg;
208 // move the pivot to a safe place and setup sentinels
209 std::swap(*beg, *pivot);
210 if (less(key(end), key(beg))) {
211 std::swap(*beg, *end);
217 // now the pivot won't move anymore
218 typename KeyAccess::result_type pivot_key = key(pivot);
221 do { ++beg; } while (less(key(beg), pivot_key));
222 do { --end; } while (less(pivot_key, key(end)));
223 if (!(beg < end)) return beg;
224 std::swap(*beg, *end);
227 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
229 template <typename RandomAccessIterator, typename Compare>
231 binary_partition(RandomAccessIterator beg, RandomAccessIterator end,
232 RandomAccessIterator pivot, Compare less)
234 return binary_partition(beg, end, pivot, less,
235 default_key<RandomAccessIterator>());
238 template <typename RandomAccessIterator>
240 binary_partition(RandomAccessIterator beg, RandomAccessIterator end,
241 RandomAccessIterator pivot)
243 typedef typename std::iterator_traits<RandomAccessIterator>::value_type
245 return binary_partition(beg, end, pivot, std::less<key_type>(),
246 default_key<RandomAccessIterator>());
250 //----------------------------------------------------------------------
251 // function ternary_partition
253 // Partitions the input range [beg,end) into three parts according to
254 // comparisons to the pivot: | less | equal | greater |
255 // Returns the middle (equal) range.
256 // PRECONDITION: pivot is in the range [beg,end)
259 // The algorithm maintains the following invariant:
261 // | equal | less | unknown | greater | equal |
263 // beg first_less left right last_greater end
265 //----------------------------------------------------------------------
266 template <typename RandomAccessIterator, typename Compare,
268 std::pair<RandomAccessIterator,RandomAccessIterator>
269 ternary_partition(RandomAccessIterator beg, RandomAccessIterator end,
270 RandomAccessIterator pivot, Compare less,
273 RandomAccessIterator left = beg, right = end-1;
274 RandomAccessIterator first_less = left, last_greater = right;
276 // first move pivot to a safe place and setup sentinels
277 std::iter_swap(pivot, left);
278 if (less(key(right), key(left))) {
279 std::iter_swap(left, right);
281 ++left; --right; --last_greater;
284 ++left; ++first_less;
287 // now the pivot won't move anymore
288 typename KeyAccess::result_type pivot_key = key(pivot);
291 while(less(key(left), pivot_key)) ++left;
292 while (!less(pivot_key, key(left)) && left < right) {
293 std::iter_swap(left++, first_less++);
294 while(less(key(left), pivot_key)) ++left;
296 while(less(pivot_key, key(right))) --right;
297 while (!less(key(right), pivot_key) && left < right) {
298 std::iter_swap(right--, last_greater--);
299 while(less(pivot_key, key(right))) --right;
301 if (!(left < right)) break;
302 std::iter_swap(left++, right--);
305 // now the situation is this:
307 // | equal | less | greater | equal |
309 // beg first_less right left last_greater end
313 // | equal | less |=| greater | equal |
315 // beg first_less left last_greater end
318 // next: swap equal parts to the middle
320 typename std::iterator_traits<RandomAccessIterator>::difference_type size;
321 size = std::min(first_less-beg, left-first_less);
322 std::swap_ranges(beg, beg+size, left-size);
323 size = std::min(end-1-last_greater, last_greater-right);
324 std::swap_ranges(right+1, right+1+size, end-size);
325 return std::make_pair(beg+(left-first_less), end-(last_greater-right));
327 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
329 template <typename RandomAccessIterator, typename Compare>
330 std::pair<RandomAccessIterator,RandomAccessIterator>
331 ternary_partition(RandomAccessIterator beg, RandomAccessIterator end,
332 RandomAccessIterator pivot, Compare less)
334 return ternary_partition(beg, end, pivot, less,
335 default_key<RandomAccessIterator>());
338 template <typename RandomAccessIterator>
339 std::pair<RandomAccessIterator,RandomAccessIterator>
340 ternary_partition(RandomAccessIterator beg, RandomAccessIterator end,
341 RandomAccessIterator pivot)
343 typedef typename std::iterator_traits<RandomAccessIterator>::value_type
345 return ternary_partition(beg, end, pivot, std::less<key_type>(),
346 default_key<RandomAccessIterator>());
350 //======================================================================
352 //======================================================================
354 //----------------------------------------------------------------------
355 // function insertion_sort
357 //----------------------------------------------------------------------
358 template <typename RandomAccessIterator, typename Compare,
361 insertion_sort(RandomAccessIterator beg, RandomAccessIterator end,
362 Compare less, KeyAccess key)
364 if (end-beg <= 1) return;
365 for (RandomAccessIterator i = beg+1; i != end; ++i) {
366 typename KeyAccess::result_type i_key = key(i); // i is not moved ...
367 RandomAccessIterator j = i-1;
368 if (!less(i_key, key(j))) continue;
369 for ( ; j != beg; --j) {
370 if (!less(i_key, key(j-1))) break;
371 std::swap(*(j-1), *j);
373 std::swap(*i, *j); // ... until here
376 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
378 template <typename RandomAccessIterator, typename Compare>
380 insertion_sort(RandomAccessIterator beg, RandomAccessIterator end,
383 insertion_sort(beg, end, less, default_key<RandomAccessIterator>());
386 template <typename RandomAccessIterator>
388 insertion_sort(RandomAccessIterator beg, RandomAccessIterator end)
390 typedef typename std::iterator_traits<RandomAccessIterator>::value_type
392 insertion_sort(beg, end, std::less<key_type>(),
393 default_key<RandomAccessIterator>());
397 //----------------------------------------------------------------------
398 // function quicksort
400 //----------------------------------------------------------------------
401 template <typename RandomAccessIterator, typename Compare,
404 quicksort(RandomAccessIterator beg, RandomAccessIterator end,
405 Compare less, KeyAccess key)
407 while (end-beg > 15) {
408 RandomAccessIterator pivot = random_pivot(beg, end, less, key);
409 RandomAccessIterator mid = binary_partition(beg, end, pivot, less, key);
410 quicksort(beg, mid, less, key);
413 insertion_sort(beg, end, less, key);
415 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
417 template <typename RandomAccessIterator, typename Compare>
419 quicksort(RandomAccessIterator beg, RandomAccessIterator end, Compare less)
421 quicksort(beg, end, less, default_key<RandomAccessIterator>());
424 template <typename RandomAccessIterator>
426 quicksort(RandomAccessIterator beg, RandomAccessIterator end)
428 typedef typename std::iterator_traits<RandomAccessIterator>::value_type
430 quicksort(beg, end, std::less<key_type>(),
431 default_key<RandomAccessIterator>());
435 #endif // PARTITION_HPP