C++ Program That Implement Radix Sort To Sort A Given List Of Integers In Ascending Order

Radix sort is an efficient, non-comparative sorting algorithm that sorts integers by processing individual digits. In this article, you will learn how to implement Radix Sort in C++ to sort a given list of integers in ascending order, understanding its mechanics and advantages.

Problem Statement

Sorting a list of integers is a fundamental task in computer science. While comparison-based sorts like Merge Sort or Quick Sort have lower bounds on their time complexity, for specific data types like non-negative integers, non-comparative algorithms such as Radix Sort can offer superior performance. The challenge lies in efficiently sorting large datasets or numbers with varying digit counts without direct comparisons between elements.

Example

Consider the following unsorted list of integers: [170, 45, 75, 90, 802, 24, 2, 66]

After applying Radix Sort in ascending order, the list will become: [2, 24, 45, 66, 75, 90, 170, 802]

Background & Knowledge Prerequisites

To understand and implement Radix Sort, you should have a basic grasp of:

• C++ Fundamentals: Variables, data types, arrays (or std::vector), loops (for, while), conditional statements, and functions.
• Counting Sort: Radix Sort internally uses Counting Sort as a subroutine to sort numbers based on individual digits. Counting Sort is a stable sorting algorithm, which means elements with equal values maintain their relative order, a crucial property for Radix Sort.

Radix Sort works by sorting elements digit by digit, starting from the least significant digit (LSD) to the most significant digit (MSD), or vice versa. The most common approach is LSD Radix Sort, which we will implement. It leverages a stable sorting algorithm (like Counting Sort) for each digit's pass.

Use Cases or Case Studies

Radix Sort is particularly useful in scenarios requiring efficient sorting of integer data:

• Sorting large datasets of non-negative integers: Its linear time complexity O(nk) (where n is the number of elements and k is the number of digits) can outperform comparison sorts for suitable data.
• Data compression algorithms: Used for sorting keys or elements that are part of the compression process.
• Fixed-length key sorting: When sorting objects based on keys of a fixed size (e.g., IP addresses, hashes, or fixed-point numbers), Radix Sort can be highly efficient.
• Specialized databases and indexing: Where records can be indexed or sorted based on integer identifiers.
• Parallel sorting: Radix Sort's digit-by-digit approach can be parallelized effectively across multiple processing units.

Solution Approaches

We will implement the Least Significant Digit (LSD) Radix Sort algorithm. This approach involves iteratively sorting the input array using Counting Sort for each digit place, starting from the units place, then tens, hundreds, and so on, until the most significant digit.

The solution consists of three main components:

1. getMax function: To find the maximum element in the array, which helps determine the number of passes (i.e., the maximum number of digits).
2. countingSort function: A stable sorting algorithm that sorts the input array based on the digit at a specific "place value" (e.g., units, tens, hundreds).
3. radixSort function: The main orchestrator that repeatedly calls countingSort for each digit place.

Approach 1: Implementing LSD Radix Sort

This approach breaks down Radix Sort into its core helper functions and then combines them.

One-line summary

Radix Sort uses Counting Sort iteratively to sort numbers digit by digit, from least to most significant.

Code example

// Radix Sort Implementation
#include <iostream>
#include <vector>
#include <algorithm> // Required for std::max_element

// Function to get the maximum value from an array
int getMax(const std::vector<int>& arr) {
    int maxVal = arr[0];
    for (size_t i = 1; i < arr.size(); ++i) {
        if (arr[i] > maxVal) {
            maxVal = arr[i];
        }
    }
    return maxVal;
}

// A function to do counting sort of arr[] according to
// the digit represented by exp.
void countingSort(std::vector<int>& arr, int exp) {
    int n = arr.size();
    std::vector<int> output(n); // Output array
    std::vector<int> count(10, 0); // Count array for digits 0-9

    // Store count of occurrences in count[]
    for (int i = 0; i < n; ++i) {
        count[(arr[i] / exp) % 10]++;
    }

    // Change count[i] so that count[i] now contains actual
    // position of this digit in output[]
    for (int i = 1; i < 10; ++i) {
        count[i] += count[i - 1];
    }

    // Build the output array
    // Iterate from right to left to ensure stability
    for (int i = n - 1; i >= 0; --i) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    // Copy the output array to arr[], so that arr[] now
    // contains sorted numbers according to current digit
    for (int i = 0; i < n; ++i) {
        arr[i] = output[i];
    }
}

// The main function to that sorts arr[] of size n using Radix Sort
void radixSort(std::vector<int>& arr) {
    // Find the maximum number to know number of digits
    int m = getMax(arr);

    // Do counting sort for every digit. Note that exp is 10^i
    // where i is current digit number
    for (int exp = 1; m / exp > 0; exp *= 10) {
        countingSort(arr, exp);
    }
}

int main() {
    // Step 1: Initialize an array of integers
    std::vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};
    
    std::cout << "Original array: ";
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // Step 2: Call Radix Sort to sort the array
    radixSort(arr);

    // Step 3: Print the sorted array
    std::cout << "Sorted array: ";
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // Test with another array
    std::vector<int> arr2 = {329, 457, 657, 839, 436, 720, 355};
    std::cout << "\\nOriginal array 2: ";
    for (int x : arr2) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    radixSort(arr2);
    std::cout << "Sorted array 2: ";
    for (int x : arr2) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

Run

Sample output

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

Original array 2: 329 457 657 839 436 720 355 
Sorted array 2: 329 355 436 457 657 720 839

Stepwise explanation for clarity

1. getMax(const std::vector& arr) function:

• This helper function iterates through the input array to find the largest integer.
• The maximum value is essential because its number of digits determines how many passes Radix Sort needs to perform (one pass for each digit place).

1. countingSort(std::vector& arr, int exp) function:

• This function sorts the arr based on the digit at the place value specified by exp (e.g., exp = 1 for units, exp = 10 for tens, exp = 100 for hundreds).
• It initializes a count array of size 10 (for digits 0-9) and an output array of the same size as arr.
• It populates count by tallying the occurrences of each digit at the exp place. For example, (arr[i] / exp) % 10 extracts the relevant digit.
• The count array is then modified to store the actual position of each digit in the output array.
• It iterates through the input array from right to left (n-1 to 0) to build the output array. This reverse iteration ensures the stability of Counting Sort, preserving the relative order of equal elements.
• Finally, the sorted elements from output are copied back into arr.

1. radixSort(std::vector& arr) function:

• This is the main function. It first calls getMax to find the largest element (m).
• It then enters a for loop that iterates with exp values 1, 10, 100, ... until m / exp becomes 0 (meaning all digit places of the maximum number have been processed).
• In each iteration, it calls countingSort with the current arr and exp. This sorts the array based on the digit at the exp place, moving from least significant to most significant.

1. main() function:

• Demonstrates how to use radixSort by initializing a std::vector of integers.
• Prints the original array.
• Calls radixSort to sort the array.
• Prints the sorted array.
• Includes a second test case for further verification.

Conclusion

Radix Sort is a powerful non-comparative sorting algorithm particularly well-suited for sorting lists of non-negative integers. By leveraging a stable sorting subroutine like Counting Sort, it efficiently arranges elements digit by digit, from least to most significant. Its time complexity, O(nk), makes it a competitive choice for specific data distributions, often outperforming comparison-based sorts when the number of digits (k) is small or constant relative to the number of elements (n).

Summary

• Radix Sort is a non-comparative integer sorting algorithm.
• It sorts numbers by processing individual digits, typically from least significant to most significant (LSD Radix Sort).
• It requires a stable sorting algorithm, such as Counting Sort, as a subroutine for each digit pass.
• The implementation involves:
• Finding the maximum element to determine the number of digit passes.
• A countingSort function to sort based on a specific digit place.
• A radixSort function to orchestrate the digit-by-digit sorting.
• Its time complexity is O(nk), where n is the number of elements and k is the maximum number of digits in any number.
• Radix Sort is highly efficient for large datasets of integers with a limited range of digits.