Radix Sort

Radix Sort

Description: Radix sort is a non-comparative sorting algorithm that sorts numbers by processing individual digits. It groups numbers by each digit, starting from the least significant digit (LSD) to the most significant digit (MSD), or vice versa. Radix sort is particularly effective for sorting large sets of integers or strings.

How It Works

1. Determine Maximum Digits: Find the maximum number in the array to know how many digits need to be processed.
2. Counting Sort by Digit: For each digit, use counting sort (or another stable sorting algorithm) to sort the array based on that digit.
   • Starting with the least significant digit, sort all numbers by that digit.
   • Move to the next significant digit and repeat until the most significant digit is processed.

Time Complexity

• Worst Case: $O(nk)$ — where $n$ is the number of elements and $k$ is the number of digits in the largest number.
• Average Case: $O(nk)$
• Best Case: $O(nk)$

Space Complexity

• Space Complexity: $O(n + k)$ — extra space is needed for the counting sort.

Stability

• Stability: Radix sort is a stable sorting algorithm, meaning it preserves the relative order of equal elements.

Example Code

Here's a C++ implementation of radix sort using counting sort as a subroutine:

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

// A function to do counting sort based on the digit represented by exp
void countingSort(vector<int>& arr, int n, int exp) {
    vector<int> output(n); // output array
    int count[10] = {0}; // count array for digits (0-9)

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

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

    // Build the 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 the output array to arr[], so that arr[] now contains sorted numbers according to the current digit
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// The main function to implement radix sort
void radixSort(vector<int>& arr) {
    int n = arr.size();
    
    // Find the maximum number to know the number of digits
    int maxVal = *max_element(arr.begin(), arr.end());

    // Apply counting sort for each digit
    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        countingSort(arr, n, exp);
    }
}

int main() {
    vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};
    radixSort(arr);

    cout << "Sorted array: ";
    for (int i : arr) {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}

Explanation of the Code

1. Function Definitions:

   • countingSort: A helper function that sorts the array based on the digit represented by exp.
   • radixSort: The main function that sorts the array using radix sort.

2. Counting Sort Process:

   • The countingSort function counts how many times each digit appears and calculates their positions in the output array.
   • The output array is built by placing elements in their correct positions based on the current digit.

3. Radix Sort Logic:

   • The radixSort function first finds the maximum value in the array to determine how many digits need sorting.
   • It then calls the counting sort for each digit, increasing the place value (units, tens, hundreds, etc.) with each iteration.

4. Output: After sorting, the program prints the sorted array.

Conclusion

Radix sort is an efficient sorting algorithm for large datasets of integers or strings with a fixed number of digits. Its linear time complexity for certain datasets makes it faster than comparison-based algorithms for sorting numbers. Radix sort's stability also makes it suitable for applications where the relative order of equal elements must be preserved. However, it may require additional memory for counting and output arrays.