OGS
quicksort.h
Go to the documentation of this file.
1
13#pragma once
14
15#include <algorithm>
16#include <cassert>
17#include <cstddef>
18#include <iterator>
19#include <vector>
20
21namespace BaseLib
22{
25template <typename It1, typename It2, typename Comparator>
26void quicksort(It1 first1, It1 last1, It2 first2, Comparator compare)
27{
28 using T1 = typename std::iterator_traits<It1>::value_type;
29 using T2 = typename std::iterator_traits<It2>::value_type;
30
31 std::vector<std::pair<T1, T2>> data;
32 data.reserve(std::distance(first1, last1));
33 std::transform(first1, last1, first2, std::back_inserter(data),
34 [](T1 const& t1, T2 const& t2)
35 { return std::make_pair(t1, t2); });
36
37 // Sort data using first element of the pair.
38 std::sort(begin(data), end(data), compare);
39
40 // Unzip sorted data.
41 for (auto const& pair : data)
42 {
43 *first1 = pair.first;
44 *first2 = pair.second;
45 ++first1;
46 ++first2;
47 }
48}
51template <typename It1, typename It2>
52void quicksort(It1 first1, It1 last1, It2 first2)
53{
54 using T1 = typename std::iterator_traits<It1>::value_type;
55 using T2 = typename std::iterator_traits<It2>::value_type;
56
57 quicksort(first1, last1, first2,
58 [](std::pair<T1, T2> const& a, std::pair<T1, T2> const& b)
59 { return a.first < b.first; });
60}
61
63template <typename T1, typename T2 = std::size_t>
64void quicksort(T1* array, std::size_t beg, std::size_t end, T2* perm)
65{
66 assert(beg <= end);
67
68 quicksort(array + beg, array + end, perm + beg);
69}
70
71template <typename T1, typename T2 = std::size_t>
72void quicksort(std::vector<T1>& array, std::size_t beg, std::size_t end,
73 std::vector<T2>& perm)
74{
75 assert(beg <= end);
76 assert(end <= array.size());
77 assert(perm.size() == array.size());
78
79 quicksort(array.data(), beg, end, perm.data());
80}
81
82template <typename T1, typename T2 = std::size_t>
83void quicksort(std::vector<T1*>& array, std::size_t beg, std::size_t end,
84 std::vector<T2>& perm)
85{
86 assert(beg <= end);
87 assert(end <= array.size());
88 assert(perm.size() == array.size());
89
90 // Zip input arrays.
91 std::vector<std::pair<T1*, T2>> data;
92 data.reserve(end - beg);
93 std::transform(array.begin() + beg, array.begin() + end, perm.begin() + beg,
94 std::back_inserter(data),
95 [](T1* const& t1, T2 const& t2)
96 { return std::make_pair(t1, t2); });
97
98 // Sort data using first element of the pair.
99 std::sort(data.begin(), data.end(),
100 [](std::pair<T1*, T2> const& a, std::pair<T1*, T2> const& b)
101 { return (*a.first < *b.first); });
102
103 // Unzip sorted data.
104 for (std::size_t i = 0; i < data.size(); i++)
105 {
106 array[beg + i] = data[i].first;
107 perm[beg + i] = data[i].second;
108 }
109}
110
111} // end namespace BaseLib
void quicksort(It1 first1, It1 last1, It2 first2, Comparator compare)
Definition quicksort.h:26