Implementation


#include <iostream>
using namespace std;

int getMax(int a[], int n)
{
    int max = a[0];
    for (int i = 1; i < n; i++)
    {
        if (a[i] > max)
            max = a[i];
    }
    return max;
}

void countingSort(int a[], int n, int pos)
{
    int output[n + 1];
    int count[10] = {0};

    // Calculate count of elements
    for (int i = 0; i < n; i++)
        count[(a[i] / pos) % 10]++;

    // Calculate cumulative frequency
    for (int i = 1; i < 10; i++)
        count[i] = count[i] + count[i - 1];

    // pos the elements in sorted order
    for (int i = n - 1; i >= 0; i--)
    {
        // count[(a[i] / pos) % 10]--;
        // output[count[(a[i] / pos) % 10]] = a[i];

        // or

        output[--count[(a[i] / pos) % 10]] = a[i];
    }

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


void radixsort(int a[], int n)
{
    int max = getMax(a, n);
    for (int pos = 1; max / pos > 0; pos *= 10)
        countingSort(a, n, pos);
}
    // Driver code
    int main()
    {
    int a[] = {471, 479, 280, 111, 135, 926, 604, 878, 112};
    int n = 9;
    radixsort(a, n);
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
    return 0;
    }

Output


  Sorted array: 111 112 135 280 471 479 604 878 926