S
S
K
```/**
* @file
* @author [Suyash Jaiswal](https://github.com/Suyashjaiswal)
* @details
* Sort the vector of unsigned integers using radix sort i.e. sorting digit by
* digit using [Counting Sort](https://en.wikipedia.org/wiki/Counting_sort) as
* subroutine. Running time of radix sort is O(d*(n+b)) where b is the base for
* representing numbers and d in the max digits in input integers and n is
* number of unsigned integers. consider example for n = 5, aray elements =
* 432,234,143,332,123 sorting digit by digit sorting according to 1) 1st digit
* place
* => 432, 332, 143, 123, 234
*
* 2) 2nd digit place
* => 123, 432, 332, 234, 143
*
* 3) 3rd digit place
* => 123, 143, 234, 332, 432
*
* using count sort at each step, which is stable.
* stable => already sorted according to previous digits.
*/

#include <algorithm>  /// for collection of functions
#include <cassert>  /// for a macro called assert which can be used to verify assumptions
#include <iostream>  /// for io operations
#include <vector>    /// for std::vector

/**
* @namespace sorting
* @brief Sorting algorithms
*/
namespace sorting {
/**
* algorithm
*/
/**
* @brief Function to sort vector according to current digit using stable
* sorting.
* @param cur_digit - sort according to the cur_digit
* @param ar - vector to be sorted
* @returns std::vector sorted till ith digit
*/
std::vector<uint64_t> step_ith(
uint16_t cur_digit,
const std::vector<uint64_t>& ar) {  // sorting according to current digit.
int n = ar.size();
std::vector<uint32_t> position(10, 0);
for (int i = 0; i < n; ++i) {
position[(ar[i] / cur_digit) %
10]++;  // counting frequency of 0-9 at cur_digit.
}
int cur = 0;
for (int i = 0; i < 10; ++i) {
int a = position[i];
position[i] = cur;  // assingning starting position of 0-9.
cur += a;
}
std::vector<uint64_t> temp(n);
for (int i = 0; i < n; ++i) {
temp[position[(ar[i] / cur_digit) % 10]] =
ar[i];  // storing ar[i] in ar[i]'s cur_digit expected position of
// this step.
position[(ar[i] / cur_digit) %
10]++;  // incrementing ar[i]'s cur_digit position by 1, as
// current place used by ar[i].
}
return temp;
}
/**
* @brief Function to sort vector digit by digit.
* @param ar - vector to be sorted
* @returns sorted vector
*/
uint64_t max_ele =
*max_element(ar.begin(), ar.end());  // returns the max element.
std::vector<uint64_t> temp = ar;
for (int i = 1; max_ele / i > 0;
i *= 10) {  // loop breaks when i > max_ele because no further digits
// left to makes changes in aray.
temp = step_ith(i, temp);
}
for (uint64_t i : temp) {
std::cout << i << " ";
}
std::cout << "\n";
return temp;
}
}  // namespace sorting

/**
* @brief Function to test the above algorithm
* @returns none
*/
static void tests() {
/// Test 1
std::vector<uint64_t> ar1 = {432, 234, 143, 332, 123};
assert(std::is_sorted(ar1.begin(), ar1.end()));
/// Test 2
std::vector<uint64_t> ar2 = {213, 3214, 123, 111, 112, 142,
133, 132,  32,  12,  113};