raddix.hxx
Go to the documentation of this file.
1 /*===========================================================================================================
2  *
3  * HUC - Hurna Core
4  *
5  * Copyright (c) Michael Jeulin-Lagarrigue
6  *
7  * Licensed under the MIT License, you may not use this file except in compliance with the License.
8  * You may obtain a copy of the License at
9  *
10  * https://github.com/Hurna/Hurna-Core/blob/master/LICENSE
11  *
12  * Unless required by applicable law or agreed to in writing, software distributed under the License is
13  * distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and limitations under the License.
15  *
16  * The above copyright notice and this permission notice shall be included in all copies or
17  * substantial portions of the Software.
18  *
19  *=========================================================================================================*/
20 #ifndef MODULE_SORT_RADDIX_HXX
21 #define MODULE_SORT_RADDIX_HXX
22 
23 // STD includes
24 #include <queue>
25 #include <vector>
26 
27 namespace huc
28 {
29  namespace sort
30  {
44  template <typename IT>
45  void RaddixSort(const IT& begin, const IT& end, unsigned int base = 10)
46  {
47  if (std::distance(begin, end) < 2)
48  return;
49 
50  // Create a bucket for each possible value of a digit
51  std::vector<std::queue<typename std::iterator_traits<IT>::value_type>> buckets(base);
52 
53  // For all possible digit
54  for (size_t powBase = 1;
55  powBase < std::numeric_limits<typename std::iterator_traits<IT>::value_type>::max();
56  powBase *= base)
57  {
58  // Push each number into the bucket of its digit value
59  for (auto it = begin; it != end; ++it)
60  buckets[static_cast<int>(*it / powBase) % base].push(*it);
61 
62  // Dequeu back all the values
63  auto itSrc = begin;
64  for (auto it = buckets.begin(); it != buckets.end(); ++it)
65  while (!it->empty())
66  {
67  *(itSrc++) = it->front();
68  it->pop();
69  }
70  }
71  }
72  }
73 }
74 
75 #endif // MODULE_SORT_RADDIX_HXX
void RaddixSort(const IT &begin, const IT &end, unsigned int base=10)
Definition: raddix.hxx:45