Radix Sort in C++

Radix Sort Algorithm in C++ (Complete Implementation).

AdvancedSorting & Searching ProgramsExample 7 of 13

radix-sort.cpp

1#include <iostream>
2#include <algorithm>
3using namespace std;
4
5int getMax(int arr[], int n) {
6    int max = arr[0];
7    for (int i = 1; i < n; i++) {
8        if (arr[i] > max)
9            max = arr[i];
10    }
11    return max;
12}
13
14void countSort(int arr[], int n, int exp) {
15    int output[n];
16    int count[10] = {0};
17    
18    // Store count of occurrences
19    for (int i = 0; i < n; i++)
20        count[(arr[i] / exp) % 10]++;
21    
22    // Change count to position
23    for (int i = 1; i < 10; i++)
24        count[i] += count[i - 1];
25    
26    // Build output array
27    for (int i = n - 1; i >= 0; i--) {
28        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
29        count[(arr[i] / exp) % 10]--;
30    }
31    
32    // Copy output to original array
33    for (int i = 0; i < n; i++)
34        arr[i] = output[i];
35}
36
37void radixSort(int arr[], int n) {
38    int max = getMax(arr, n);
39    
40    // Do counting sort for every digit
41    for (int exp = 1; max / exp > 0; exp *= 10)
42        countSort(arr, n, exp);
43}
44
45void printArray(int arr[], int n) {
46    for (int i = 0; i < n; i++) {
47        cout << arr[i] << " ";
48    }
49    cout << endl;
50}
51
52int main() {
53    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
54    int n = sizeof(arr) / sizeof(arr[0]);
55    
56    cout << "Original array: ";
57    printArray(arr, n);
58    
59    radixSort(arr, n);
60    
61    cout << "Sorted array: ";
62    printArray(arr, n);
63    
64    return 0;
65}

Output

Original array: 170 45 75 90 802 24 2 66
Sorted array: 2 24 45 66 75 90 170 802

What's going on

The program sorts an array of integers using the Radix Sort algorithm. For example:

Input array: [170, 45, 75, 90, 802, 24, 2, 66]

Output array: [2, 24, 45, 66, 75, 90, 170, 802]

Radix Sort processes digits from right to left (least significant to most significant), using Counting Sort for each digit position.

Header Files Used

1.#include <iostream>

Provides cout and cin for input/output operations.

2.#include <algorithm>

Provides max_element() and min_element() functions (used in some implementations).

Understanding Radix Sort

Algorithm Concept

Sorts by processing individual digits

Starts with least significant digit (rightmost)

Moves to more significant digits (leftward)

Uses Counting Sort for each digit position

Stable sorting algorithm

Visual Example

Array: [170, 45, 75, 90, 802, 24, 2, 66]

Pass 1 (ones place): [170, 90, 802, 2, 24, 45, 75, 66]

Pass 2 (tens place): [802, 2, 24, 45, 66, 170, 75, 90]

Pass 3 (hundreds place): [2, 24, 45, 66, 75, 90, 170, 802]

Function: getMax()

int getMax(int arr[], int n) {

int max = arr[0];

for (int i = 1; i < n; i++) {

if (arr[i] > max)

max = arr[i];

}

1return max;

How it works

Finds the maximum element in the array

Needed to determine number of digits to process

Example: max = 802 → 3 digits → 3 passes needed

Function: countSort()

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]++;

// Change count to position

for (int i = 1; i < 10; i++)

count[i] += count[i - 1];

// Build output array

for (int i = n - 1; i >= 0; i--) {

output[count[(arr[i] / exp) % 10] - 1] = arr[i];

count[(arr[i] / exp) % 10]--;

}

// Copy output to original array

for (int i = 0; i < n; i++)

arr[i] = output[i];

}

1// Store count of occurrences

How it works

exp: current digit position (1, 10, 100, ...)

(arr[i] / exp) % 10: extracts digit at current position

Uses Counting Sort for the current digit

Maintains stability by processing from right to left

Example

(exp = 1, ones place):

Extract ones digit: 170 → 0, 45 → 5, 75 → 5

Count occurrences: count[0]=1, count[5]=2, ...

Build sorted output based on ones digit

Function: radixSort()

void radixSort(int arr[], int n) {

int max = getMax(arr, n);

for (int exp = 1; max / exp > 0; exp *= 10)

countSort(arr, n, exp);

}

How it works

Gets maximum element to determine number of passes

exp starts at 1 (ones place)

Each iteration: exp *= 10 (tens, hundreds, ...)

Continues until max / exp > 0 (all digits processed)

Example

(max = 802):

Pass 1: exp = 1 (ones place)

Pass 2: exp = 10 (tens place)

Pass 3: exp = 100 (hundreds place)

Pass 4: exp = 1000, max/exp = 0 → stop

Time and Space Complexity

Time Complexity

: O(d * (n + k))

d: number of digits in maximum element

n: number of elements

k: range of digits (0-9, so k = 10)

Each pass: O(n + k) for Counting Sort

Total: O(d * (n + k)) ≈ O(d * n) for integers

Space Complexity

: O(n + k)

Output array: O(n)

Count array: O(k) = O(10) = O(1)

Total: O(n)

Stability

: Stable

Counting Sort maintains relative order

Important for sorting objects with multiple fields

When to Use Radix Sort

Best For

Integers with limited digit range

When number of digits is small compared to array size

When stability is required

Fixed-width integers

Not Recommended For

Floating-point numbers (without modification)

Strings (requires different approach)

Very large digit ranges

When d is large (many passes needed)

Important Considerations

Digit Extraction

(arr[i] / exp) % 10 extracts digit at position exp

exp = 1: ones place

exp = 10: tens place

exp = 100: hundreds place

Stability

Processing from right to left (i = n-1 to 0) maintains stability

Equal digits preserve relative order from previous pass

Number of Passes

Determined by maximum element's digit count

Example: max = 802 → 3 passes

Example: max = 9999 → 4 passes

return 0;

This ends the program successfully.

PreviousHeap Sort NextCounting Sort