Radix Sort Algorithm

Radix Sort Algorithm

1. Overview

Radix Sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by individual digits which share the same significant position and value. It processes the digits either from least significant digit (LSD) to most significant digit (MSD), or vice versa. The most common implementation is LSD Radix Sort.

2. Algorithm Details

  1. Find the maximum number maxVal in the array to know the number of digits.
  2. Initialize exp = 1 (100 place).
  3. While maxVal / exp > 0:
    • Perform a stable counting sort on the array based on the digit at exp.
    • Multiply exp by the base (10 for decimal).

3. Time and Memory Complexity

  • Time Complexity: O(d · (n + b)), where:
    • n = number of elements
    • d = number of digits in the maximum number
    • b = base (e.g., 10 for decimal)
  • Memory Complexity: O(n + b), for the output array and the count array.

4. Easy Problems

4.1. Sort an Array of Non-Negative Integers

Given an array of non-negative integers, sort them in ascending order.

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

void countingSort(vector<int>& arr, int exp) {
    int n = arr.size();
    vector<int> output(n);
    int count[10] = {0};

    for (int i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;

    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }

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

void radixSort(vector<int>& arr) {
    int maxVal = *max_element(arr.begin(), arr.end());
    for (int exp = 1; maxVal / exp > 0; exp *= 10)
        countingSort(arr, exp);
}

int main() {
    vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};
    radixSort(arr);
    for (int num : arr)
        cout << num << " ";
    return 0;
}

4.2. Sort Strings of Equal Length

Given an array of lowercase strings of equal length, sort them lexicographically.

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

void countingSortByChar(vector<string>& arr, int pos) {
    int n = arr.size();
    vector<string> output(n);
    int count[26] = {0};

    for (int i = 0; i < n; i++)
        count[arr[i][pos] - 'a']++;

    for (int i = 1; i < 26; i++)
        count[i] += count[i - 1];

    for (int i = n - 1; i >= 0; i--) {
        int idx = arr[i][pos] - 'a';
        output[count[idx] - 1] = arr[i];
        count[idx]--;
    }

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

void radixSortStrings(vector<string>& arr) {
    if (arr.empty()) return;
    int length = arr[0].size();
    for (int pos = length - 1; pos >= 0; pos--)
        countingSortByChar(arr, pos);
}

int main() {
    vector<string> arr = {"bca", "acb", "abc", "bac", "cab", "cba"};
    radixSortStrings(arr);
    for (auto &s : arr)
        cout << s << " ";
    return 0;
}

5. Intermediate Problems

5.1. Sort Large Range of Integers with Negative Values

Modify Radix Sort to handle negative integers by offsetting.

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

void countingSortOffset(vector<int>& arr, int exp, int offset) {
    int n = arr.size();
    vector<int> output(n);
    vector<int> count(10, 0);

    for (int i = 0; i < n; i++)
        count[((arr[i] + offset) / exp) % 10]++;

    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    for (int i = n - 1; i >= 0; i--) {
        int idx = ((arr[i] + offset) / exp) % 10;
        output[count[idx] - 1] = arr[i];
        count[idx]--;
    }

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

void radixSortWithNegatives(vector<int>& arr) {
    int minVal = *min_element(arr.begin(), arr.end());
    int maxVal = *max_element(arr.begin(), arr.end());
    int offset = -minVal;
    maxVal += offset;

    for (int exp = 1; maxVal / exp > 0; exp *= 10)
        countingSortOffset(arr, exp, offset);
}

int main() {
    vector<int> arr = { -10, 7, 3, -1, 0, -20, 5 };
    radixSortWithNegatives(arr);
    for (int x : arr)
        cout << x << " ";
    return 0;
}

5.2. Sort Floating-Point Numbers (Fixed Decimal Places)

Sort floats by scaling to integers.

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

void radixSortFloats(vector<double>& arr, int places) {
    int n = arr.size();
    double scale = pow(10, places);
    vector<int> intArr(n);
    for (int i = 0; i < n; i++)
        intArr[i] = int(arr[i] * scale);

    // reuse previous radix for ints
    int maxVal = *max_element(intArr.begin(), intArr.end());
    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        vector<int> output(n);
        int count[10] = {0};
        for (int i = 0; i < n; i++)
            count[(intArr[i] / exp) % 10]++;
        for (int i = 1; i < 10; i++)
            count[i] += count[i - 1];
        for (int i = n - 1; i >= 0; i--) {
            int d = (intArr[i] / exp) % 10;
            output[count[d] - 1] = intArr[i];
            count[d]--;
        }
        for (int i = 0; i < n; i++)
            intArr[i] = output[i];
    }

    for (int i = 0; i < n; i++)
        cout << (double)intArr[i] / scale << " ";
}

int main() {
    vector<double> arr = { 3.14, 2.71, 1.41, 0.57 };
    radixSortFloats(arr, 2);
    return 0;
}

6. Hard Problem

6.1. Sort Very Large Numbers (Strings of Up to 106 Digits)

When numbers exceed built-in types, treat them as strings and use MSD Radix Sort recursively.

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

void msdRadixSort(vector<string>& arr, int left, int right, int d) {
    if (left >= right) return;
    vector<int> count(11, 0); // 0-9 digits + 1 for shorter strings
    vector<string> output(right - left + 1);

    for (int i = left; i <= right; i++) {
        int c = (d < arr[i].size()) ? arr[i][d] - '0' + 1 : 0;
        count[c]++;
    }
    for (int i = 1; i < 11; i++)
        count[i] += count[i - 1];

    for (int i = right; i >= left; i--) {
        int c = (d < arr[i].size()) ? arr[i][d] - '0' + 1 : 0;
        output[count[c] - 1] = arr[i];
        count[c]--;
    }
    for (int i = left; i <= right; i++)
        arr[i] = output[i - left];

    int start = left;
    for (int i = 0; i < 11; i++) {
        int end = left + count[i] - (i > 0 ? count[i-1] : 0) - 1;
        if (start <= end)
            msdRadixSort(arr, start, end, d + 1);
        start = end + 1;
    }
}

int main() {
    vector<string> arr = {
        "12345678901234567890",
        "1234567890",
        "98765432109876543210",
        "1234567890123456789"
    };
    msdRadixSort(arr, 0, arr.size() - 1, 0);
    for (auto &s : arr)
        cout << s << "\n";
    return 0;
}

7. Conclusion

Radix Sort is very efficient for keys that can be represented as digits or fixed-length strings. Its linear time behavior makes it useful for large datasets where comparison-based sorts may be slower.