partition.hxx
Go to the documentation of this file.
1 /*===========================================================================================================
2  *
3  * SHA - Simple Hybesis Algorithms
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/michael-jeulinl/Simple-Hybesis-Algorithms/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_PARTITION_HXX
21 #define MODULE_SORT_PARTITION_HXX
22 
23 // STD includes
24 #include <iterator>
25 
26 namespace SHA_Sort
27 {
43  template <typename IT, typename Compare = std::less_equal<typename std::iterator_traits<IT>::value_type>>
44  IT Partition(const IT& begin, const IT& pivot, const IT& end)
45  {
46  if (std::distance(begin, end) < 2 || pivot == end)
47  return pivot;
48 
49  auto pivotValue = *pivot; // Keep the pivot value;
50  std::swap(*pivot, *(end - 1)); // Put the pivot at the end for convenience
51  auto store = begin; // Put the store pointer at the beginning
52 
53  // Swap each smaller before the pivot item
54  for (auto it = begin; it != end - 1; ++it)
55  {
56  if (Compare()(*it, pivotValue))
57  {
58  std::swap(*store, *it);
59  ++store;
60  }
61  }
62 
63  // Replace the pivot at its good position
64  std::swap(*(end - 1), *store);
65 
66  return store;
67  }
68 }
69 
70 #endif // MODULE_SORT_PARTITION_HXX
IT Partition(const IT &begin, const IT &pivot, const IT &end)
Definition: partition.hxx:44