radix_sort_v1.cpp

// This is a code on how to perform a Radix Sort.

#include <iostream>
#include <algorithm>
using namespace std;

void countSort(int arr[], int n, int exp) {
    int output[n];
    int count[10] = {0};

    for (int i = 0; i < n; i++) count[(arr[i] / exp) % 10]++;

    for (int i = 1; i < 10; i++) count[i] += count[i - 1];

    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    for (int i = 0; i < n; i++) arr[i] = output[i];
}

void radixSort(int arr[], int n) {
    int m = *max_element(arr, arr + n);

    for (int exp = 1; m / exp > 0; exp *= 10) countSort(arr, n, exp);
}

int main() {
    int n;
    cin >> n;

    int a[n];
    for (int i = 0; i < n; ++i) cin >> a[i];

    radixSort(a, n);

    for (int i = 0; i < n; ++i) cout << a[i] << " ";

    return 0;
}