Radix Sort Algorithm in DSA C++ - Execution Trace

Concept Flow - Radix Sort Algorithm

Find max number to know max digits

↓

For each digit place from LSD to MSD

↓

Place numbers into buckets by current digit

↓

Collect numbers from buckets in order

↓

Repeat for next digit place

↓

Sorted array obtained

Radix sort processes digits from least to most significant, grouping numbers by each digit and collecting them repeatedly until fully sorted.

Execution Sample

DSA C++

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

Sorts array by processing digits from least significant to most significant using counting sort as a subroutine.

Execution Table

Step	Operation	Digit Place (exp)	Buckets (0-9)	Array State After Collection	Notes
1	Find max number	-	-	-	Max number is 802
2	Process digit place	1 (units)	[170, 90, 802, 2, 24, 45, 75, 66]	[170, 90, 802, 2, 24, 45, 75, 66]	Bucketed by units digit
3	Process digit place	10 (tens)	[802, 2, 24, 45, 66, 170, 75, 90]	[802, 2, 24, 45, 66, 170, 75, 90]	Bucketed by tens digit
4	Process digit place	100 (hundreds)	[2, 24, 45, 66, 75, 90, 170, 802]	[2, 24, 45, 66, 75, 90, 170, 802]	Bucketed by hundreds digit
5	Check next digit place	1000	-	-	max / 1000 > 0? No, stop sorting

💡 No more digits to process, array is sorted

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
arr	[170, 45, 75, 90, 802, 24, 2, 66]	[170, 45, 75, 90, 802, 24, 2, 66]	[170, 90, 802, 2, 24, 45, 75, 66]	[802, 2, 24, 45, 66, 170, 75, 90]	[2, 24, 45, 66, 75, 90, 170, 802]	[2, 24, 45, 66, 75, 90, 170, 802]
max	N/A	802	802	802	802	802
exp	N/A	1	10	100	1000	1000

Key Moments - 3 Insights

Why do we start sorting from the least significant digit (units place)?

Because radix sort relies on stable sorting at each digit place, starting from the least significant digit ensures that the order of digits processed earlier is preserved, as shown in steps 2 to 4 in the execution_table.

What happens if the max number has fewer digits than others?

Digits beyond the max number's length are treated as zero, so those numbers go into the zero bucket. This is why in step 4, numbers with no hundreds digit are placed correctly.

Why do we stop when exp (digit place) exceeds max number?

Because no more digits exist beyond the max number's length, so further passes won't change the order. Step 5 shows this check and stops the sorting.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what is the array state after collecting from buckets?

A [802, 2, 24, 45, 66, 170, 75, 90]

B [2, 24, 45, 66, 75, 90, 170, 802]

C [170, 90, 802, 2, 24, 45, 75, 66]

D [170, 45, 75, 90, 802, 24, 2, 66]

💡 Hint

Check the 'Array State After Collection' column in execution_table row for step 2

At which digit place does the array become fully sorted?

A 100 (hundreds)

B 10 (tens)

C 1 (units)

D 1000 (thousands)

💡 Hint

Look at the final array state after step 4 in execution_table

If the max number was 99 instead of 170, how many digit places would radix sort process?

A 1

B 2

C 3

D 4

💡 Hint

Radix sort processes digits until exp > max; 99 has 2 digits, so steps for exp=1 and exp=10

Concept Snapshot

Radix Sort Algorithm:
- Sorts numbers digit by digit from least to most significant
- Uses stable sorting (like counting sort) at each digit
- Stops when digit place exceeds max number's digits
- Efficient for sorting integers with known digit length
- Time complexity: O(d*(n+b)) where d=digits, n=array size, b=bucket count

Full Transcript

Radix sort finds the maximum number to determine how many digits to process. It sorts the array by each digit place starting from the least significant digit (units), placing numbers into buckets based on the current digit. After collecting numbers from buckets, it moves to the next digit place (tens, hundreds, etc.). This repeats until all digit places are processed, resulting in a sorted array. The process preserves order by using stable sorting at each step. The example array is sorted in three passes for units, tens, and hundreds digits. The algorithm stops when the digit place exceeds the maximum number's digit length.

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