RadixSort.cpp

//
//  main.cpp
//  RadixSort
//
//  Created by Phil Kirby on 12/5/24.
//

#include <iostream>
#include <unordered_map>
#include <vector>
#include <map>
#include <print>
#include <thread>
#include <future>

using namespace std;

int getDigit(int num, int exponent);
vector<int> create(vector<int> values, int exponent);
void getDigits(int num);
vector<int> mapToVector(map<int, vector<int>> map);
void printVector(const string label, vector<int> vec);
int countDigit(int n);
vector<int> stableRadixSort(vector<int> nums);
vector<int> parallel_process(vector<int> nums);

int main(int argc, const char * argv[]) {
    // insert code here...
    std::cout << "Hello, World!\n";
    vector<int> nums = { 170, 45, 75, 8765, 90, 802, 24, 34550, 2, 66 };
//    vector<int> nums = { 1, 5, 2, 4, 3 };
    
//    stableRadixSort(nums);
    vector<int> result = parallel_process(nums);
    
    printVector("result: ", result);
    
    return 0;
}

vector<int> stableRadixSort(vector<int> nums) {
    int max = *max_element(nums.begin(), nums.end());
    int maxDigits = countDigit(max);
    
    cout << "max: " << max << "\n";
    cout << "maxDigits: " << maxDigits << "\n";

    vector<int> vals = nums;
    
    for (int i = 0; i < maxDigits; i++) {
        vals = create(vals, i);
        std::string label;
        label += "exponent: ";
        label += std::to_string(i);
        
        printVector(label, vals);
    }
    
    return vals;
}

vector<int> parallel_process(vector<int> nums) {
    // get even and odd values from nums
    vector<int> evenNumbers;
    vector<int> oddNumbers;
    
    for (auto num : nums) {
        if ((num % 2) == 0) { evenNumbers.push_back(num); }
        else { oddNumbers.push_back(num); }
    }
    
    // process both on their own thread
    auto evenFuture = std::async(stableRadixSort, evenNumbers);
    auto oddFuture = std::async(stableRadixSort, oddNumbers);
    
    vector<int> evenResult = evenFuture.get();
    vector<int> oddResult = oddFuture.get();
    
    std::vector<int> ret;

    for (int num : evenResult) {
        ret.push_back(num);
    }

    for (int num : oddResult) {
        ret.push_back(num);
    }
    
    return ret;
}

void getDigits(int num) {
    int one = getDigit(num, 0);
    int ten = getDigit(num, 1);
    int hun = getDigit(num, 2);
    
    cout << num << " : " << one << " " << ten << " " << hun << "\n";
}

int getDigit(int num, int exponent) {
    const int base = 10;
    int div = pow(base, exponent);
    int digit = (num / div) % base;
    
    return digit;
}

vector<int> create(vector<int> values, int exponent) {
    vector<int> ret = vector<int>();
    map<int, vector<int>> map;
    
    // Make sure we have values & exponent
    if (values.size() == 0) { return ret; }
    if (exponent < 0) { return ret; }
    
    // Iterate over values vector
    for (auto i : values) {
        int digit = getDigit(i, exponent);
        
        if (map.find(digit) != map.end()) {
            vector<int> existingValues = map[digit];
            existingValues.push_back(i);
            map[digit] = existingValues;
        } else {
            vector<int> newValues = vector<int>();
            newValues.push_back(i);
            map[digit] = newValues;
        }
    }
    
    ret = mapToVector(map);
    
    return ret;
}

vector<int> mapToVector(map<int, vector<int>> map) {
    vector<int> ret = vector<int>();
    
    for (const auto& pair : map) {
        vector<int> vals = pair.second;
        
        for (auto val : vals) {
            ret.push_back(val);
        }
    }
    
    return ret;
}

void printVector(const string label, vector<int> vec) {
    cout << "Thread ID: " << this_thread::get_id() << " ";
    cout << label << " ";
    
    for (const auto& val : vec) {
        cout << val << ", ";
    }
    
    cout << "\n\n";
}

int countDigit(int n) {
    if (n/10 == 0)
        return 1;
    return 1 + countDigit(n / 10);
}