]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | //Templated Spreadsort-based implementation of integer_sort |
2 | ||
3 | // Copyright Steven J. Ross 2001 - 2014. | |
4 | // Distributed under the Boost Software License, Version 1.0. | |
5 | // (See accompanying file LICENSE_1_0.txt or copy at | |
6 | // http://www.boost.org/LICENSE_1_0.txt) | |
7 | ||
8 | // See http://www.boost.org/libs/sort/ for library home page. | |
9 | ||
10 | /* | |
11 | Some improvements suggested by: | |
12 | Phil Endecott and Frank Gennari | |
13 | ||
14 | Doxygen comments by Paul A. Bristow Jan 2015 | |
15 | ||
16 | */ | |
17 | ||
18 | #ifndef BOOST_INTEGER_SORT_HPP | |
19 | #define BOOST_INTEGER_SORT_HPP | |
20 | #include <algorithm> | |
21 | #include <vector> | |
22 | #include <cstring> | |
23 | #include <limits> | |
24 | #include <boost/static_assert.hpp> | |
25 | #include <boost/sort/spreadsort/detail/constants.hpp> | |
26 | #include <boost/sort/spreadsort/detail/integer_sort.hpp> | |
27 | ||
28 | namespace boost { | |
29 | namespace sort { | |
30 | namespace spreadsort { | |
31 | //Top-level sorting call for integers. | |
32 | ||
33 | ||
34 | /*! \brief Integer sort algorithm using random access iterators. | |
35 | (All variants fall back to @c std::sort if the data size is too small, < @c detail::min_sort_size). | |
36 | ||
37 | \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm, | |
38 | which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n | |
39 | Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, | |
40 | so @c integer_sort is asymptotically faster | |
41 | than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11, | |
42 | so its worst-case with default settings for 32-bit integers is | |
43 | <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n | |
44 | Some performance plots of runtime vs. n and log(range) are provided:\n | |
45 | <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a> | |
46 | \n | |
47 | <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a> | |
48 | ||
49 | \param[in] first Iterator pointer to first element. | |
50 | \param[in] last Iterator pointing to one beyond the end of data. | |
51 | ||
52 | \pre [@c first, @c last) is a valid range. | |
53 | \pre @c RandomAccessIter @c value_type is mutable. | |
54 | \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a> | |
55 | \pre @c RandomAccessIter @c value_type supports the @c operator>>, | |
56 | which returns an integer-type right-shifted a specified number of bits. | |
57 | \post The elements in the range [@c first, @c last) are sorted in ascending order. | |
58 | ||
59 | \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves), | |
60 | the right shift, subtraction of right-shifted elements, functors, or any operations on iterators throw. | |
61 | ||
62 | \warning Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss. | |
63 | \warning Invalid arguments cause undefined behaviour. | |
64 | \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type, | |
65 | enabling faster generic-programming. | |
66 | ||
67 | \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: | |
68 | \remark * N is @c last - @c first, | |
69 | \remark * K is the log of the range in bits (32 for 32-bit integers using their full range), | |
70 | \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). | |
71 | ||
72 | */ | |
73 | template <class RandomAccessIter> | |
74 | inline void integer_sort(RandomAccessIter first, RandomAccessIter last) | |
75 | { | |
76 | // Don't sort if it's too small to optimize. | |
77 | if (last - first < detail::min_sort_size) | |
78 | std::sort(first, last); | |
79 | else | |
80 | detail::integer_sort(first, last, *first >> 0); | |
81 | } | |
82 | ||
83 | /*! \brief Integer sort algorithm using random access iterators with both right-shift and user-defined comparison operator. | |
84 | (All variants fall back to @c std::sort if the data size is too small, < @c detail::min_sort_size). | |
85 | ||
86 | \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm, | |
87 | which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n | |
88 | Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, | |
89 | so @c integer_sort is asymptotically faster | |
90 | than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11, | |
91 | so its worst-case with default settings for 32-bit integers is | |
92 | <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n | |
93 | Some performance plots of runtime vs. n and log(range) are provided:\n | |
94 | <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a> | |
95 | \n | |
96 | <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a> | |
97 | ||
98 | \param[in] first Iterator pointer to first element. | |
99 | \param[in] last Iterator pointing to one beyond the end of data. | |
100 | \param[in] shift Functor that returns the result of shifting the value_type right a specified number of bits. | |
101 | \param[in] comp A binary functor that returns whether the first element passed to it should go before the second in order. | |
102 | ||
103 | \pre [@c first, @c last) is a valid range. | |
104 | \pre @c RandomAccessIter @c value_type is mutable. | |
105 | \post The elements in the range [@c first, @c last) are sorted in ascending order. | |
106 | ||
107 | \return @c void. | |
108 | ||
109 | \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves), | |
110 | the right shift, subtraction of right-shifted elements, functors, | |
111 | or any operations on iterators throw. | |
112 | ||
113 | \warning Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss. | |
114 | \warning Invalid arguments cause undefined behaviour. | |
115 | \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type, | |
116 | enabling faster generic-programming. | |
117 | ||
118 | \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: | |
119 | \remark * N is @c last - @c first, | |
120 | \remark * K is the log of the range in bits (32 for 32-bit integers using their full range), | |
121 | \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). | |
122 | */ | |
123 | template <class RandomAccessIter, class Right_shift, class Compare> | |
124 | inline void integer_sort(RandomAccessIter first, RandomAccessIter last, | |
125 | Right_shift shift, Compare comp) { | |
126 | if (last - first < detail::min_sort_size) | |
127 | std::sort(first, last, comp); | |
128 | else | |
129 | detail::integer_sort(first, last, shift(*first, 0), shift, comp); | |
130 | } | |
131 | ||
132 | /*! \brief Integer sort algorithm using random access iterators with just right-shift functor. | |
133 | (All variants fall back to @c std::sort if the data size is too small, < @c detail::min_sort_size). | |
134 | ||
135 | \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm, | |
136 | which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n | |
137 | ||
138 | \par Performance: | |
139 | Worst-case performance is <em> O(N * (lg(range)/s + s)) </em>, | |
140 | so @c integer_sort is asymptotically faster | |
141 | than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11, | |
142 | so its worst-case with default settings for 32-bit integers is | |
143 | <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n | |
144 | Some performance plots of runtime vs. n and log(range) are provided:\n | |
145 | * <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a>\n | |
146 | * <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a> | |
147 | ||
148 | \param[in] first Iterator pointer to first element. | |
149 | \param[in] last Iterator pointing to one beyond the end of data. | |
150 | \param[in] shift A functor that returns the result of shifting the value_type right a specified number of bits. | |
151 | ||
152 | \pre [@c first, @c last) is a valid range. | |
153 | \pre @c RandomAccessIter @c value_type is mutable. | |
154 | \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a> | |
155 | \post The elements in the range [@c first, @c last) are sorted in ascending order. | |
156 | ||
157 | \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves), | |
158 | the right shift, subtraction of right-shifted elements, functors, | |
159 | or any operations on iterators throw. | |
160 | ||
161 | \warning Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss. | |
162 | \warning Invalid arguments cause undefined behaviour. | |
163 | \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type, | |
164 | enabling faster generic-programming. | |
165 | ||
166 | \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where: | |
167 | \remark * N is @c last - @c first, | |
168 | \remark * K is the log of the range in bits (32 for 32-bit integers using their full range), | |
169 | \remark * S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size). | |
170 | ||
171 | */ | |
172 | template <class RandomAccessIter, class Right_shift> | |
173 | inline void integer_sort(RandomAccessIter first, RandomAccessIter last, | |
174 | Right_shift shift) { | |
175 | if (last - first < detail::min_sort_size) | |
176 | std::sort(first, last); | |
177 | else | |
178 | detail::integer_sort(first, last, shift(*first, 0), shift); | |
179 | } | |
180 | } | |
181 | } | |
182 | } | |
183 | ||
184 | #endif | |
185 |