radix_sort.cpp

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int fillZeroAndI(vector<string> & nums){
    size_t max = 0;
    for(size_t i = 0; i < nums.size(); i++){ //Find max num size.
        if(nums[i].size() > max) max = nums[i].size();
    }
    for(size_t i = 0; i < nums.size(); i++){ //Fill in zeros
        if (nums[i].size() < max) {
            nums[i] = string(max - nums[i].size(), '0') + nums[i];
        }
    }
    return max;
}

void radixSort(vector<string> & nums){
    int iterations = fillZeroAndI(nums); //Fills smaller sized numbers to lead with 0's so that all num sizes are equal.
    for(int i = iterations-1; i >= 0; i--){ //Do counting sort on Ith digit (Left-Right = MSD).
        vector<int> freqArray(10,0);
        for(size_t j = 0; j < nums.size(); j++){ //Set frequency array for count sort.
			int ctoi = nums[j][i] - '0';
			freqArray[ctoi]++;
		}
		vector<int> cummulationArray(10);
		cummulationArray[0] = freqArray[0];
		for(size_t j = 1; j < freqArray.size(); j++){ //Set cummulation array for count sort.
			cummulationArray[j] = cummulationArray[j-1] + freqArray[j];
		}
		vector<string> sorted(nums.size());
		for(int j = nums.size()-1; j >= 0; j--){
            int ctoi = nums[j][i] - '0'; //digit
            sorted[cummulationArray[ctoi]-1] = nums[j];
            cummulationArray[ctoi]--;
        }
		nums = sorted;
    }
}

int main() { //Gets numbers in base ten and sorts via radix sort.
	int c, n;
	vector<string> nums;
	cin >> c;
	for(int i = 0; i < c; i++){
	    cin >> n;
	    nums.push_back(to_string(n));
	}
	if(nums.size() > 1){
		radixSort(nums);
		cout << "Sorted List: ";
		for(size_t i = 0; i < nums.size(); i++) cout << nums[i] << " ";
		cout << endl;
	}
	else{
		cout << "Sorted List: ";
		if(nums.size() == 1) cout << nums[0] << " ";
		cout << endl;
	}
    return 0;
}