Radix Sort

 

 

 

#include <bits/stdc++.h>


std::vector<int> countingSortByDigit(std::vector<int> & nums, int digit) {
    int counts[10] = {0, };
    for (int num : nums) {
        int count_idx = num / (int)std::pow(10, digit) % 10;
        ++counts[count_idx];
    }

    std::vector<int> acc_counts;
    int acc_count = 0;

    for (int count : counts) {
        acc_count += count;
        acc_counts.push_back(acc_count);
    }

    std::vector<int> end_locs;
    for (int c : acc_counts) {
        end_locs.push_back(c - 1);
    }

    std::vector<int> sorted(nums.size());
    for (int i = nums.size() - 1; i >= 0; --i) {
        int count_idx = nums[i] / (int)std::pow(10, digit) % 10;
        int end_loc = end_locs[count_idx];
        sorted[end_loc] = nums[i];
        --end_locs[count_idx];
    }
    return sorted;
}


void RadixSort(std::vector<int> & arr) {

    int largest_num = *std::max_element(arr.begin(), arr.end());
    int digits = (int)std::log10(largest_num) + 1;
    std::vector<int> sorted = arr;
    for (int digit = 0; digit < digits; ++digit) {
        sorted = countingSortByDigit(sorted, digit);
    }
    arr = sorted;
}




void printArr(std::vector<int> arr){
    for (auto ele : arr) {
        std::cout << ele << " ";
    }
    std::cout << "\n";
}



int main(int argc, char** argv) {

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::vector<int> arr = {391, 582, 50, 924, 8, 192};
    std::cout << "before : ";
    printArr(arr);
    
    RadixSort(arr);

    std::cout << "after  : ";
    printArr(arr);
	return 0;
}

 

 

정리

시간복잡도 : O(w *(n + k))   w는 자릿수,  k (0 ~ 9) 분류할 기준 갯수

공간복잡도 : O(max(n, k))

Stable : O