Counting Radix Sort: A C++ version

Question

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:

1. Tidied up the View into a single class.
2. Used the std::partial_sum() algorithm
3. 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:

1. Only works for integer types with even number of bytes.
2. Only works for unsigned values
3. 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";
}

Answer 1

The assumption that CHAR_BIT is 8 can be avoided.

I'm not convinced it's necessary to use the exact-width type std::uint64_t. We could go for std::uint_fast64_t. In any case, remember to include <cstdint> to bring in the definitions. Looking further, that type is used for a count of elements that are in memory - I think std::size_t is most appropriate there.

std::array has a member count() (which is what std::count() will call). It's arguably clearer to use that rather than the general function. We forgot to include <algorithm> for std::count() and std::partial_sum().

I'm not sure I like the single View class that does both forward and reverse views. I appreciate that this is something a previous reviewer encouraged, but I think it might be simpler with a simple (unidirectional) View and an adaptor something like:

template<typename It>  // "std::bidirectional_iterator It" in C++20
struct ReverseView: View<std::reverse_iterator<It>>
{
    ReverseView(It beg, It end)
      : View{std::make_reverse_iterator(end),
             std::make_reverse_iterator(beg)}
    {}
};

Or even just a simple function:

auto make_reverse_view(auto beg, auto end)
{
    return View{std::make_reverse_iterator(end),
                std::make_reverse_iterator(beg)};
}

It might be possible to support unsigned and floating-point types (assuming IEEE-754 or some other representation where floats sort "naturally") by reinterpreting values as unsigned char[]. Obviously, that would allow users to pass non-ordered values such as std::complex, but we could add a constraint (std::enable_if in C++17) to restrict to std::is_arithmetic types.

I don't think it's too hard to make this work (rather than UB) with odd-sized value types, simply by checking to see whether we've finished between the two operations:

auto radix_func = [](unsigned index) {
        return [index](Type const& value){
                return (value >> (index * CHAR_BIT)) & UCHAR_MAX;
            };
    };

for (auto index = 0u;  index < sizeof (Type);  ++index) {
    // Use counting sort from src ⟶ output then output ⟶ src
    // The result is that the result will be an in-place sort.
    csort(begin, end, output.begin(), output.end(), radix_func(index));
    if (++index == sizeof (Type)) {
        std::copy(output.begin(), output.end(), begin);
    } else {
        csort(output.begin(), output.end(), begin, end, radix_func(index));
    }
}