Radix sort with C++

Question

At first the input array is traversed and for each number the lsb is found. Then the number is put into appropriate bucket according to it. For example for an input array { 123, 45}, at first 123 will be put into bucket 3 (because 123 % 10 == 3). 45 goes to bucket 5. Then after first pass, the input array is cleared and again filled with numbers from the bucket. For the second pass, 123 will be put into bucket 2 and 45 into bucket 4. This continues until the 123 mod is 0.

Can you please review my code?

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdexcept>

class RadixSort
{
public:
    RadixSort(){};
    virtual ~RadixSort(){};

    void sort(std::vector<int> &nums);

private:
    int maxNum,div;
    std::vector<std::vector<int> > buckets;

};

void RadixSort::sort(std::vector<int> &nums)
{
    if(nums.empty())
        return;

    buckets.resize(10);
    maxNum = *(std::max_element(nums.begin(),nums.end()));

    int i=1;
    while(maxNum != 0)
    {
       // Move numbers into appropriate buckets
       for(auto num : nums)
       {
          if(num<0)
            throw std::domain_error("For radix sort , array cannot contain negative value. ");

          int remainder = (num/i)%10;
          buckets[remainder].push_back(num);
       }

       // Now, move numbers from bucket to original array
       nums.clear();
       for(auto bucket1:buckets)
       {
           for(auto bucket2: bucket1)
           {
               nums.push_back(bucket2);
           }

       }
       for(int j=0; j<10; j++)
       {
          buckets[j].clear();
       }

       maxNum/=10;
       i *= 10;
    }
}

void test(const std::string &testName, std::vector<int>&input, const std::vector<int>&output)
{
    RadixSort rs;
    rs.sort(input);
    std::cout<<testName;
    if(input == output)
        std::cout<<" passed. ";
    else
        std::cout<<" failed. ";

    std::cout<<"\n";
}

int main()
{
    std::vector<int>input = {4,90,0};
    std::vector<int>output = {0,4,90};
    test("Test 1",input,output);

    input = {};
    output = {};
    test("Test 2",input,output);

    return 0;
}

Answer 1

• With C++11, you can now have right angle brackets together:

  std::vector<std::vector<int>> buckets;
  

• If the user will only need to call test(), then sort() can be private.

• Since sort() throws, its calls may need to be in try blocks so that a caught exception can be handled accordingly. But, first determine if you need it to throw.

• Some lines like these:

  int remainder = (num/i)%10;
  

  can have a little more whitespace:

  int remainder = (num / i) % 10;
  

• This can be shortened:

  if(input == output)
      std::cout<<" passed. ";
  else
      std::cout<<" failed. ";
  

  using a single-line ternary statement:

  std::cout << ((input == output) ? " passed. " : " failed. ");
  

  You could also append the "\n" to both strings instead of having a separate one.

  Moreover, the user may prefer to handle the outcome differently. As such, you may instead have test() return a bool and move the outputs to main(). This should also help keep test() clear of code not involved with the testing.

Answer 2

for(auto bucket1:buckets)
{
    for(auto bucket2: bucket1)
    {
       nums.push_back(bucket2);
    }

}

This is potentially incredibly expensive. Since auto is going to be deduced to a std::vector> on the outside, and a std::vector on the inside, a ton of unnecessary copies are being made. Since you're only reading from the values, they should instead be const ref (i.e. const auto&).

---

bucket2 is a pretty misleading name since it's actually the value stored in the bucket.

---

Do you plan on RadixSort being extended? If so, I would expect sort() to be virtual. If not, I would expect the destructor to not be virtual.

---

I'm not sure if this is really a good fit for OOP. The class is essentially only being used to house what could otherwise be local variables to sort(). The only advantage I see is that the allocation overhead of buckets gets avoided, but there are ways to avoid that with a free function as well (though none particularly pleasant...).

I guess my questions are essentially: Are you really going to reuse RadixSort instances? Do RadixSort instances have any kind of state? If you're answer to both of those is no, it likely doesn't need to be a class.

---

for(int j=0; j<10; j++)
{
   buckets[j].clear();
}

Though in this case it's very unlikely to change, in general, it's a bad idea to hard code sizes. It would be better to use size(), or better yet, to use a for each loop:

for (auto bucket& : buckets) {
    bucket.clear();
}

And really, you don't need to loop over buckets again. You can do it in the outer loop of the nested loops you have above it.

---

Profiling would have to be done to confirm this, but I suspect that checking all of the numbers up front for negatives would be more efficient than having an if in every single iteration. Then again, there's a million factors at play with things like that, so I may be completely wrong. Also, this is likely not a level of performance you need to worry about (and if it is, you should be using a well tested, widely used, efficiently oriented radix sort).

---

Some of your levels of indention seem to be 3 spaces. That's rather non-standard in the C++ world. All of your indention levels should be either 4 spaces or tabs. (Maybe CodeReview just botched it? Sometimes it seems to do strange things to code formatting :/)

Answer 3

My suggestions:

1. You don't need the class Radix. You just need a function (or couple of overloaded functions), radix_sort.

2. You can easily use a function template that can be used to sort random access containers of any integral types.

Here's your function adapted to be function template, with test code:

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdexcept>
#include <type_traits>

template <typename RandomIt >
void radix_sort(RandomIt first, RandomIt last)
{
   if ( first == last )
      return;

   typedef typename std::iterator_traits<RandomIt>::value_type ValueType;
   static_assert(std::is_integral<ValueType>::value, "Radix sort requires integral value types.");

   ValueType maxValue = *(std::max_element(first, last));
   ValueType div{};
   std::vector<std::vector<ValueType>> buckets(10);

   ValueType i=1;
   while ( maxValue != 0 )
   {
       // Move numbers into appropriate buckets
       for(RandomIt iter = first; iter != last; ++iter )
       {
          ValueType num = *iter;
          if(num<0)
            throw std::domain_error("For radix sort , array cannot contain negative value. ");

          ValueType remainder = (num/i)%10;
          buckets[remainder].push_back(num);
       }

       // Now, move numbers from bucket to original array
       RandomIt iter = first;
       for(auto const& bucket1:buckets)
       {
           for(auto value: bucket1)
           {
              *iter = value;
              ++iter;
           }

       }
       for(int j=0; j<10; j++)
       {
          buckets[j].clear();
       }

       maxValue /= 10;
       i *= 10;
    }
}

template <typename  RandomAccessContainer>
void radix_sort(RandomAccessContainer& container)
{
   radix_sort(std::begin(container), std::end(container));
}

void test1()
{
   // Sort vector of ints.
   std::vector<int>input = {4,90,0};
   std::vector<int>output = {0,4,90};
   radix_sort(input);
   bool passed = (input == output);
   std::cout << "Test 1" << (passed ? " passed.\n" : " failed.\n");
}

void test2()
{
   // Sort empty vector of ints.
   std::vector<int>input = {};
   std::vector<int>output = {};
   radix_sort(input);
   bool passed = (input == output);
   std::cout << "Test 2" << (passed ? " passed.\n" : " failed.\n");
}

void test3()
{
   // Sort an array of ints.
   int input[] = {4,90,0};
   int output[] = {0,4,90};
   radix_sort(input);
   bool passed = true;
   for ( int i = 0; i < 3; ++i )
   {
      if ( input[i] != output[i] )
      {
         passed = false;
      }
   }
   std::cout << "Test 3" << (passed ? " passed.\n" : " failed.\n");
}

void test4()
{
   // Sort a vector of unsigned longs.
   std::vector<unsigned long>input = {4,90,0};
   std::vector<unsigned long>output = {0,4,90};
   radix_sort(input);
   bool passed = (input == output);
   std::cout << "Test 4" << (passed ? " passed.\n" : " failed.\n");
}

int main()
{
   test1();
   test2();
   test3();
   test4();
   return 0;
}

Output:

Test 1 passed.
Test 2 passed.
Test 3 passed.
Test 4 passed.