2
\$\begingroup\$

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";
}
\$\endgroup\$
3
  • \$\begingroup\$ (radex index?) \$\endgroup\$
    – greybeard
    Dec 7, 2021 at 17:37
  • \$\begingroup\$ @greybeard That's the problem when I first try something new; I don't yet know all the correct terminology. So radix is basically a variant of bucket sort, so here I am referring to the value we use to determine the bucket the value is placed into (ie the index of the bucket). \$\endgroup\$ Dec 7, 2021 at 17:43
  • \$\begingroup\$ i.e. First call to csort() uses the lowest significant byte as the bucket index. Second call to csort() uses the next byte in each value. etc. \$\endgroup\$ Dec 7, 2021 at 17:46

1 Answer 1

2
\$\begingroup\$

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));
    }
}
\$\endgroup\$
4
  • \$\begingroup\$ To solve the odd number, I was thinking along the same lines. But reduce the iterations of the loop by one set of two and then move the test outside the loop. This then allows for the use if constexpr () so the compiler can optimize it out correctly. \$\endgroup\$ Dec 13, 2021 at 22:10
  • \$\begingroup\$ Why don't you like the single View class? I thought that was a rather clever idea. :-( I particularly like the self documenting usage: make_View<Forward>() and make_View<Reverse>() \$\endgroup\$ Dec 13, 2021 at 22:12
  • \$\begingroup\$ I'm sorry. If it helps, I also think it's clever. Experience has taught me that being clever is a seductive trap, though. Can't remember who first observed it, but something like "given that debugging/maintenance is twice as hard as writing new code, that makes one's cleverest code impossible to fix." Or something like that. Your idea of using if constexpr for the odd size loop is great - I didn't see that at all. \$\endgroup\$ Dec 14, 2021 at 8:02
  • \$\begingroup\$ Well lets hope my cleverness is overridden soon. I wish my standard compiler supported ranges already but here we are in 2021 and C++20 is not full supported by clang on mac. Boo. \$\endgroup\$ Dec 14, 2021 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.