Follow up to original question:
This is Radix Sort, using a counting implementation. For numbers that are N bytes in length, we use an N pass counting approach. Starting with the least significant byte we do a counting sort of all the values. We then repeat the counting sort using each consecutively higher byte in the values as the index.
Only have access to C++17 (so added some view objects (that I believe are available in C++20).
Comment on anything appreciated.
Based on the previous review by JDługosz:
- Tidied up the
View
into a single class. - Used the
std::partial_sum()
algorithm - Abstracted the key calculation into lambda.
Then by moving the counting sort portion into its own function, I have removed the need for a copy as the calls to csort()
are done in pairs. The first copies it to the temporary storage, the second copies it back to the source.
Issues that I need to address:
- Only works for integer types with even number of bytes.
- Only works for unsigned values
- If the input iterators are Random Access this is quick and simple,
but lists may be less efficient. Can it be made better for them?
Views
#include <iostream>
#include <vector>
#include <array>
#include <numeric>
// A way to make a normal or a reverse view from iterators.
// Makes using the Range based `for()` easier rather than having
// to manually work with the iterators themselves.
enum ViewType {Forward, Reverse};
template<ViewType V, typename I>
struct View
{
I beginRange;
I endRange;
using ForwardI = I;
using ReverseI = std::reverse_iterator<I>;
auto begin() {if constexpr (V == Forward) {return beginRange;} else {return ReverseI(endRange);}}
auto end() {if constexpr (V == Forward) {return endRange;} else {return ReverseI(beginRange);}}
};
// Helper function to make view without need to know type.
template<ViewType V, typename I>
View<V, I> make_View(I begin, I end) {return View<V, I>{begin, end};}
Counting Sort
template<typename I1, typename I2, typename A>
void csort(I1 beginSrc, I1 endSrc, I2 beginDst, I2 endDst, A const& index)
{
// Keep track of counts for each radix value.
// Since we are using bytes we need 256 values 0->255
std::array<std::uint64_t, 0x100> count{};
// Step 1: Count each radix value.
// Complexity O(n)
for (auto const& value: make_View<Forward>(beginSrc, endSrc)) {
++count[ index(value) ];
}
// Step 2: Calculate prefix value.
// Effectively if we do a count sort this is the
// one past the end of the range for this value
// of radix to be stored.
// Complexity O(1) assuming 255 is small compared to n
std::partial_sum(std::begin(count), std::end(count), std::begin(count));
// Step 3: Copy from the input to output by
// using the radex index (do in reverse order).
// Complexity O(n)
for (auto const& value: make_View<Reverse>(beginSrc, endSrc)) {
std::uint64_t& offset = count[ index(value) ];
--offset;
beginDst[offset] = value;
}
// Step 4: Copy output back to the input.
// Removed. As this function is called in pairs.
// First time copies to the intermediate the second copies back to src.
}
Radix Sort
// Only works for unsigned values.
// Only works for types that have an even number of bytes.
template<typename I>
void rsort(I begin, I end)
{
// Create an intermediate output container.
using Type = typename std::iterator_traits<I>::value_type;
std::vector<Type> output(std::distance(begin, end));
// A loop to loop over each byte as the radex index.
// Note: We make the assumption that there is a multiple of 2 bytes in the src data
// Probably need to add some template stuff to check for 1 byte values and handle separately.
for (int index = 0; index < sizeof(Type); index += 2) {
// Use counting sort from src -> output then output->src
// The result is that the result will be an in-place sort.
csort(begin, end, std::begin(output), std::end(output), [index](Type const& value){return (value >> ((index+0) * 8)) & 0xFF;});
csort(std::begin(output), std::end(output), begin, end, [index](Type const& value){return (value >> ((index+1) * 8)) & 0xFF;});
}
}
Test Harness
int main()
{
std::vector<int> data{4583,182,5433,8092,11465,6614,29731,24061,29432,24542,32685,9724,31005,456,29255,25325,30048,18875,27775,30360,13531,1029,5715,3729,31680,22998,2359,29525,15433,7106,20196,11561,20578,14325,231,6835,8729,22579,21733,21845,28353,25495,8623,32589,4329,24583,10505,22413,32000,28538,12858,12123,23749,25833,16723,7593,30064,11542,30528,3122,17570,1792,26256,31321,13,18465,26884,4544,25571,10349,16857,26795,31744,21003,6357,3603,21462,12498,6675,15242,14620,15746,18063,18642,32054,16583,16753,15675,24931,18926};
rsort(std::begin(data), std::end(data));
std::cout << "[ ";
char sep = ' ';
for (auto const& v: data) {
std::cout << sep << " " << v;
sep = ',';
}
std::cout << " ]\n";
}
radex index
?) \$\endgroup\$csort()
uses the lowest significant byte as the bucket index. Second call tocsort()
uses the next byte in each value. etc. \$\endgroup\$