C++ Implementation of Radix Sort Algorithm¶

What is Radix Sort?¶

Radix Sort is a non-comparative integer sorting algorithm that works by sorting digits bit by bit. Unlike comparison-based sorting algorithms such as Bubble Sort or Quick Sort, Radix Sort does not compare element values directly. Instead, it sorts elements based on each digit (e.g., units, tens, hundreds place) and achieves overall order through successive digit-wise sorting.

Basic Idea of Radix Sort¶

Radix Sort typically uses the Least Significant Digit (LSD) first approach, starting from the least significant digit (units place) and proceeding to the most significant digit (e.g., hundreds, thousands place). For each digit, a stable sorting algorithm (like Counting Sort) is used to handle the distribution of current-digit values, ensuring that results from lower-digit sorting remain intact during higher-digit sorting.

Implementation Steps¶

1. Find the Maximum Number: Determine the number of digits in the largest element of the array. For example, if the maximum number is 802 (3 digits), digits in the units, tens, and hundreds places need to be processed.
2. Sort Digit by Digit: Perform Counting Sort for each digit (from least significant to most significant):
   - Count the frequency of each digit (0-9) at the current position.
   - Calculate prefix sums to determine the position of each digit in the temporary array.
   - Traverse the original array from right to left, placing elements into the temporary array according to their current digit to maintain stability.
   - Copy the temporary array back to the original array to complete sorting for the current digit.

C++ Code Implementation¶

#include <iostream>
using namespace std;

// Helper function: Counting Sort (sorts by the current digit)
void countingSort(int arr[], int n, int exp) {
    int output[n];  // Temporary array to store sorted results
    int count[10] = {0};  // Count array to store frequency of digits 0-9

    // 1. Count frequency of each digit at the current position
    for (int i = 0; i < n; i++) {
        int digit = (arr[i] / exp) % 10;  // Extract current digit
        count[digit]++;
    }

    // 2. Compute prefix sums to determine positions of each digit
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    // 3. Place elements into temporary array (stable sorting by traversing right to left)
    for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10;
        output[count[digit] - 1] = arr[i];  // Place at correct position
        count[digit]--;  // Ensure subsequent elements don't overwrite
    }

    // 4. Copy sorted temporary array back to original array
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// Main Radix Sort function
void radixSort(int arr[], int n) {
    // 1. Find the maximum number to determine the number of digits
    int max_num = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max_num) {
            max_num = arr[i];
        }
    }

    // 2. Sort each digit from least significant to most significant
    for (int exp = 1; max_num / exp > 0; exp *= 10) {
        countingSort(arr, n, exp);
    }
}

// Helper function to print array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Array before sorting: ";
    printArray(arr, n);

    radixSort(arr, n);

    cout << "Array after sorting: ";
    printArray(arr, n);

    return 0;
}

Code Explanation¶

1. countingSort Function:
   - Counts the frequency of each digit (0-9) at the current position (determined by exp, e.g., exp=1 for the units place).
   - Uses prefix sums to calculate the position of each digit in the temporary array, ensuring stability.
   - Traverses the original array from right to left to place elements in the temporary array without overwriting already sorted elements.
   - Copies the sorted temporary array back to the original array to complete the current digit’s sorting.

2. radixSort Function:
   - Finds the maximum element to determine the highest digit to process.
   - Calls countingSort iteratively for each digit (from least to most significant) to sort the array digit by digit.

Test Results¶

Running the code produces the following output:

Array before sorting: 170 45 75 90 802 24 2 66 
Array after sorting: 2 24 45 66 75 90 170 802 

Summary¶

Radix Sort achieves sorting by decomposing numbers into digits and using Counting Sort. Its time complexity is O(d×(n+k)) (where d is the number of digits, n is the array length, and k is the radix, typically 10). It is efficient for large integer ranges and leverages the stability of Counting Sort to preserve lower-digit order during higher-digit sorting. Beginners can master Radix Sort by understanding the step-by-step digit-wise processing.