C++ - Radix sort implementation

Question

I have the following radix sort implementation:

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <cstddef>
#include <algorithm>

void radix_sort(std::vector<int>& arr)
{
    int radix = 1;
    // Largest element in unsorted array
    int max = *(std::max_element(arr.begin(), arr.end()));
    while(max / radix)
    {
        // Buckets used for sorting. Each bucket representing a digit.
        std::vector<std::vector<int>> buckets(10, std::vector<int>());
        for(const auto& num : arr)
        {
            int digit = num / radix % 10;
            buckets[digit].push_back(num);
        }
        std::size_t k = 0;
        // Take the elements out of buckets into the array
        for(std::size_t i = 0; i < 10; i++)
        {
            for(std::size_t j = 0; j < buckets[i].size(); j++)
            {
                arr[k] = buckets[i][j];
                k++;
            }
        }
        // Change the place of digit used for sorting
        radix *= 10;
    }

}

// Function to print array
void print_arr(std::vector<int>& arr)
{
    for(auto elem : arr)
    {
        std::cout << elem << "\t";
    }
    std::cout << "\n";
}

int main()
{
    std::vector<int> arr;
    std::string s;
    std::cout << "Enter the elements: " << std::endl;
    std::getline(std::cin, s);
    std::istringstream ss(s);
    int val;
    while(ss >> val)
    {
        arr.push_back(val);
    }
    std::cout << "Before sorting: \n";
    print_arr(arr);
    radix_sort(arr);
    std::cout << "After sorting: \n";
    print_arr(arr);
    return 0;
}

I pass an array to the radix_sort function. It uses a variable called radix to identify the digit in a particular place (unit, ten, hundred etc.) in the number. Based on this digit, we sort elements into buckets. Once this sorting is done, the elements are taken out based on the order of bucket (The elements in zeroth bucket comes out first, followed by those in first bucket, second bucket and so on). This is repeated until all the digits in the largest element are visited.

1) I would like to know if there is a better data structure for buckets?

2) Is there a more efficient method to find largest element in the unsorted array?

3) If possible, please provide an overall review of the code.

Answer 1

A vector is usually the best data structure to use unless you have a compelling reason to use something else. Since you know how many buckets you need, one slight improvement you can make to your buckets is to use an array of vectors, rather than a vector of vectors:

std::array<std::vector<int>, 10> buckets;

This will create 10 empty vectors on the stack (without dynamically allocating those 10).

To find the largest element in an unsorted container requires looking at every element in the container. The only way to improve on that is to change your algorithm so that it does not need to know what the maximum element is; more on that below.

There are several issues with your sort. In its current form, it does not handle the trivial case of an empty arr as your scan for a maximum element will dereference the end iterator which is not allowed. Nor does it does it handle negative numbers. The % operator can return negative numbers if the numerator is negative. This will result in an out-of-bounds array element access. There will also be problems with really large numbers (greater than std::numeric_limits<int>::max() / 10).

One way to handle negative numbers is to make an initial pass where you split the array to sort into two groups, one with negative numbers and the other with non-negative numbers. Then you can radix sort each group, taking care when doing the negative numbers to keep the intermediate results properly signed.

Failing that, how can you determine when to end your loop if you don't know what the maximum element is? You can keep track as you put things into buckets. When the num / radix calculation is 0, that element will always be placed in the first (0) bucket for the rest of the sort. There may be a larger element earlier in the bucket (think of sorting {203, 3}) so it might still move. But once all elements have that term 0 then you can stop sorting.

When moving the elements out of the buckets back into the array, you can use the standard algorithms rather than using your nested for loops. The buckets[i].size() will potentially be calculated every iteration. You can use std::copy to transfer the elements:

auto k = arr.begin();
for (auto &b: buckets)
    k = std::copy(b.begin(), b.end(), k);

You should pass the parameter to print_arr as a const & (print_arr(const std::vector<int> &arr)).