Radix Sort Algorithm in DSA C++

Mental Model

Radix sort sorts numbers by processing digits from least to most significant, grouping numbers by each digit step.

Analogy: Imagine sorting mail by zip code: first by the last digit, then the second last, and so on, until fully sorted.

Array: [170, 45, 75, 90, 802, 24, 2, 66]
Buckets for digits 0-9:
0: []
1: []
2: []
3: []
4: []
5: []
6: []
7: []
8: []
9: []

Dry Run Walkthrough

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

Goal: Sort the list using radix sort by processing digits from least significant to most significant

Step 1: Sort by least significant digit (ones place)

Buckets:
0: [170, 90]
2: [802, 2]
4: [24]
5: [45, 75]
6: [66]
Others: []
Reassembled array: [170, 90, 802, 2, 24, 45, 75, 66]

Why: Group numbers by their ones digit to partially sort by that digit

Step 2: Sort by second least significant digit (tens place)

Buckets:
0: [802, 2]
2: [24]
4: [45]
6: [66]
7: [170, 75]
9: [90]
Others: []
Reassembled array: [802, 2, 24, 45, 66, 170, 75, 90]

Why: Group numbers by their tens digit to refine sorting

Step 3: Sort by third least significant digit (hundreds place)

Buckets:
0: [2, 24, 45, 66, 75, 90]
1: [170]
8: [802]
Others: []
Reassembled array: [2, 24, 45, 66, 75, 90, 170, 802]

Why: Group numbers by their hundreds digit to finalize sorting

Result:

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

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Function to get digit at given place
int getDigit(int num, int place) {
    return (num / place) % 10;
}

// Radix sort function
void radixSort(vector<int>& arr) {
    if (arr.empty()) return;
    int maxVal = *max_element(arr.begin(), arr.end());
    // Start with least significant digit place = 1
    for (int place = 1; maxVal / place > 0; place *= 10) {
        vector<vector<int>> buckets(10);
        // Place elements into buckets based on current digit
        for (int num : arr) {
            int digit = getDigit(num, place);
            buckets[digit].push_back(num);
        }
        // Reassemble array from buckets
        int index = 0;
        for (const auto& bucket : buckets) {
            for (int num : bucket) {
                arr[index++] = num;
            }
        }
    }
}

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

for (int place = 1; maxVal / place > 0; place *= 10) {

iterate over digit places from least significant to most significant

for (int num : arr) { int digit = getDigit(num, place); buckets[digit].push_back(num); }

group numbers into buckets by current digit

for (const auto& bucket : buckets) { for (int num : bucket) { arr[index++] = num; } }

reassemble array from buckets preserving order

Output

2 24 45 66 75 90 170 802 

Complexity Analysis

Time: O(d * (n + k)) where d is number of digits, n is number of elements, k is bucket count (10); because we process each digit and distribute elements into buckets

Space: O(n + k) for buckets to hold elements temporarily during sorting

vs Alternative: Compared to comparison sorts like quicksort O(n log n), radix sort can be faster for fixed digit sizes but uses extra space for buckets

Edge Cases

Empty array

Function returns immediately without error and array remains empty

DSA C++

if (arr.empty()) return;

Array with one element

Array remains unchanged after sorting

DSA C++

for (int place = 1; maxVal / place > 0; place *= 10) {

Array with duplicate numbers

Duplicates are preserved and sorted correctly

DSA C++

buckets[digit].push_back(num);

When to Use This Pattern

When you need to sort integers or fixed-length strings efficiently without comparisons, reach for radix sort because it sorts by digits in linear time.

Common Mistakes

Mistake: Not processing all digit places up to the maximum number's length
Fix: Use a loop that continues while maxVal / place > 0 to cover all digits

Mistake: Reassembling array incorrectly by mixing bucket order
Fix: Reassemble by iterating buckets in order from 0 to 9 to maintain digit order

Summary

Radix sort sorts numbers digit by digit from least to most significant.

Use it when sorting integers or fixed-length data where comparison-based sorts are slower.

The key insight is grouping numbers by each digit to gradually build a fully sorted list.

Practice

1. What is the main idea behind the Radix Sort algorithm?

easy

A. Sort numbers digit by digit starting from the least significant digit

B. Compare each element with every other element and swap if needed

C. Divide the array into halves and sort each half recursively

D. Use a pivot element to partition the array and sort partitions

Solution

1. Step 1: Understand Radix Sort approach

   Radix Sort sorts numbers by processing individual digits starting from the least significant digit (rightmost) to the most significant digit (leftmost).

2. Step 2: Compare with other sorting methods

   Other options describe Bubble Sort, Merge Sort, and Quick Sort, which are different algorithms.

3. Final Answer:

   Sort numbers digit by digit starting from the least significant digit -> Option A

4. Quick Check:

   Radix Sort = Digit by digit sorting [OK]

Hint: Radix Sort processes digits from right to left [OK]

Common Mistakes:

• Confusing Radix Sort with comparison-based sorts
• Thinking it sorts from most significant digit first
• Assuming it uses swapping of elements

2. Which of the following is the correct way to extract the digit at position pos (starting from 0 for least significant digit) from an integer num in C++?

easy

A. (num / (10 * pos)) % 10

B. ((num / (int)pow(10, pos)) % 10)

C. (num % (10 * pos)) / 10

D. (num % pow(10, pos)) / 10

Solution

1. Step 1: Understand digit extraction formula

   To get the digit at position pos, divide num by 10^pos and then take modulo 10.

2. Step 2: Check each option

   ((num / (int)pow(10, pos)) % 10 correctly uses pow(10, pos) for exponentiation and modulo 10 to get the digit.

3. Final Answer:

   ((num / (int)pow(10, pos)) % 10) -> Option B

4. Quick Check:

   Digit extraction = (num / 10^pos) % 10 [OK]

Hint: Divide by 10^pos then mod 10 to get digit [OK]

Common Mistakes:

• Using multiplication instead of exponentiation
• Incorrect order of operations
• Using modulo before division

3. What will be the output of the following C++ code snippet using Radix Sort on array arr = {170, 45, 75, 90, 802, 24, 2, 66}?

void countingSort(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]++;
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];
    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

void radixSort(int arr[], int n) {
    int maxVal = *max_element(arr, arr + n);
    for (int exp = 1; maxVal / exp > 0; exp *= 10)
        countingSort(arr, n, exp);
}

int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);
    radixSort(arr, n);
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

medium

A. 24 2 45 66 75 90 170 802

B. 802 170 90 75 66 45 24 2

C. 2 24 45 66 75 90 170 802

D. 2 24 45 75 66 90 170 802

Solution

1. Step 1: Understand Radix Sort steps on given array

   Radix Sort sorts by digits: first units, then tens, then hundreds. After full sorting, array becomes sorted ascending.

2. Step 2: Trace final sorted array

   Sorted array is: 2 24 45 66 75 90 170 802.

3. Final Answer:

   2 24 45 66 75 90 170 802 -> Option C

4. Quick Check:

   Radix Sort final output = sorted array ascending [OK]

Hint: Radix Sort outputs fully sorted array ascending [OK]

Common Mistakes:

• Confusing intermediate steps with final output
• Misordering numbers with same digits
• Ignoring stable sorting in countingSort

4. Identify the bug in the following Radix Sort counting sort implementation and select the correct fix:

void countingSort(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]++;
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];
    for (int i = 0; i < n; i++) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

medium

A. Change the last for loop to iterate from n-1 down to 0 for stable sorting

B. Initialize count array with -1 instead of 0

C. Remove the cumulative sum loop for count array

D. Replace output array with a vector for dynamic sizing

Solution

1. Step 1: Identify stable sorting requirement in counting sort

   Counting sort must process elements from right to left to maintain stability.

2. Step 2: Check the for loop direction

   Current loop goes from 0 to n-1, which breaks stability. Changing it to n-1 down to 0 fixes this.

3. Final Answer:

   Change the last for loop to iterate from n-1 down to 0 for stable sorting -> Option A

4. Quick Check:

   Stable counting sort = reverse iteration [OK]

Hint: Counting sort must iterate backward for stability [OK]

Common Mistakes:

• Iterating forward breaks stable sorting
• Misunderstanding count array initialization
• Ignoring cumulative sum step

5. Given an array of strings representing numbers with leading zeros, e.g., {"002", "010", "001", "100"}, how can you adapt Radix Sort to correctly sort them as numbers?

hard

A. Use counting sort only on the first character of each string

B. Sort strings lexicographically using Radix Sort on characters

C. Ignore leading zeros and sort strings as-is with Radix Sort

D. Convert strings to integers first, then apply Radix Sort on integers

Solution

1. Step 1: Understand sorting numeric strings with leading zeros

   Sorting strings lexicographically will not sort numbers correctly if leading zeros exist.

2. Step 2: Convert strings to integers for numeric sorting

   Convert strings to integers to remove leading zeros, then apply Radix Sort on integers for correct numeric order.

3. Final Answer:

   Convert strings to integers first, then apply Radix Sort on integers -> Option D

4. Quick Check:

   Numeric string sorting = convert to int then Radix Sort [OK]

Hint: Convert strings to int before Radix Sort for numeric order [OK]

Common Mistakes:

• Sorting strings lexicographically causes wrong order
• Ignoring leading zeros impact
• Using only first character for sorting