Radix Sort Algorithm in DSA C - Execution Trace

Concept Flow - Radix Sort Algorithm

Find max number to know max digits

↓

Start with least significant digit (LSD)

↓

Place numbers into buckets by current digit

↓

Collect numbers from buckets in order

↓

Move to next more significant digit

↓

Repeat until all digits processed

↓

Sorted array ready

Radix sort processes numbers digit by digit from least to most significant, grouping by digit and collecting to sort fully.

Execution Sample

DSA C

void radixSort(int arr[], int n) {
  int max = getMax(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.

Execution Table

Step	Operation	Digit Place (exp)	Array State Before	Buckets (0-9)	Array State After
1	Find max number	-	[170, 45, 75, 90, 802, 24, 2, 66]	-	Max = 802
2	Sort by LSD (exp=1)	1	[170, 45, 75, 90, 802, 24, 2, 66]	0: [170, 90] 1: [] 2: [802, 2] 3: [] 4: [24] 5: [45, 75] 6: [66] 7: [] 8: [] 9: []	[170, 90, 802, 2, 24, 45, 75, 66]
3	Sort by 10s place (exp=10)	10	[170, 90, 802, 2, 24, 45, 75, 66]	0: [802, 2] 1: [] 2: [24] 3: [] 4: [45] 5: [] 6: [66] 7: [170, 75] 8: [] 9: [90]	[802, 2, 24, 45, 66, 170, 75, 90]
4	Sort by 100s place (exp=100)	100	[802, 2, 24, 45, 66, 170, 75, 90]	0: [2, 24, 45, 66, 75, 90] 1: [170] 2: [] 3: [] 4: [] 5: [] 6: [] 7: [] 8: [802] 9: []	[2, 24, 45, 66, 75, 90, 170, 802]
5	Check next digit (exp=1000)	1000	[2, 24, 45, 66, 75, 90, 170, 802]	-	Stop: max/exp=802/1000=0 (no more digits)

💡 Stop when max/exp is 0, meaning all digit places processed.

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 (LSD) instead of the most significant digit (MSD)?

Starting from LSD ensures that sorting by a less significant digit doesn't disturb the order established by previous digits. This is shown in execution_table rows 2 to 4 where each digit place sorting builds on the previous.

How do buckets help in sorting by each digit?

Buckets group numbers by the current digit, making it easy to collect them in sorted order. See execution_table rows 2, 3, and 4 where buckets hold numbers by digit before collecting.

When does the algorithm stop processing digits?

It stops when the current digit place (exp) is larger than the max number, so max/exp becomes 0. This is shown in execution_table row 5.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the array state after sorting by the 10s place?

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

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

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

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

💡 Hint

Check the 'Array State After' column in execution_table row 3.

At which step does the algorithm decide to stop processing digits?

A Step 5

B Step 3

C Step 4

D Step 2

💡 Hint

Look for the step where max/exp becomes 0 in execution_table.

If the max number was 99 instead of 802, how many digit places would the algorithm process?

A 1 digit place

B 2 digit places

C 3 digit places

D 4 digit places

💡 Hint

Check variable_tracker for exp values and when max/exp becomes 0.

Concept Snapshot

Radix Sort Algorithm:
- Sort numbers digit by digit from least significant to most significant.
- Use buckets (0-9) to group numbers by current digit.
- Collect numbers from buckets to form new array order.
- Repeat for each digit place until max digit processed.
- Stable and efficient for fixed digit length numbers.

Full Transcript

Radix Sort works by sorting numbers starting from the least significant digit to the most significant digit. First, it finds the maximum number to know how many digits to process. Then, for each digit place (1s, 10s, 100s, etc.), it groups numbers into buckets based on that digit. After grouping, it collects numbers from buckets in order to form a partially sorted array. This process repeats for each digit place until all digits of the largest number are processed. The final array is fully sorted. This method uses stable sorting at each digit and is efficient for numbers with fixed digit lengths.

Practice

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

easy

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

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

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

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

Solution

1. Step 1: Understand Radix Sort process

   Radix Sort sorts numbers by processing each digit from least significant to most significant.

2. Step 2: Compare with other sorting methods

   Unlike comparison-based sorts, Radix Sort uses digit positions to sort without direct comparisons.

3. Final Answer:

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

4. Quick Check:

   Radix Sort = Digit by digit sorting [OK]

Hint: Remember: Radix Sort sorts 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 pivot or recursion

2. Which of the following is the correct way to initialize the counting array for Radix Sort in C?

easy

A. int count[10] = {0};

B. int count[10]; // no initialization

C. int count[10] = {1};

D. int count[10] = NULL;

Solution

1. Step 1: Understand counting array role

   The counting array stores frequency of digits 0-9 and must start at zero.

2. Step 2: Check initialization options

   Only int count[10] = {0}; sets all elements to zero correctly in C.

3. Final Answer:

   int count[10] = {0}; -> Option A

4. Quick Check:

   Counting array must start with zeros [OK]

Hint: Initialize counting array with zeros using {0} [OK]

Common Mistakes:

• Leaving counting array uninitialized
• Initializing with all ones
• Assigning NULL to an int array

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

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr)/sizeof(arr[0]);
    radixSort(arr, n); // Assume radixSort is correctly implemented
    printArray(arr, n);
    return 0;
}

medium

A. 24 2 45 66 75 90 170 802

B. 170 45 75 90 802 24 2 66

C. 802 170 90 75 66 45 24 2

D. 2 24 45 66 75 90 170 802

Solution

1. Step 1: Understand Radix Sort output

   Radix Sort sorts the array fully in ascending order after processing all digits.

2. Step 2: Sort given array

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

3. Final Answer:

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

4. Quick Check:

   Sorted array matches 2 24 45 66 75 90 170 802 [OK]

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

Common Mistakes:

• Assuming output is unchanged
• Thinking output is reversed
• Confusing partial digit sorting with final output

4. Identify the error in this Radix Sort counting step code snippet:

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]] = arr[i];
    count[(arr[i] / exp) % 10]--;
}

medium

A. Counting array size should be 100, not 10

B. Indexing output array should be count[...] - 1

C. Loop for count prefix sum should start from 0

D. Division by exp should be replaced by modulo exp

Solution

1. Step 1: Analyze output array indexing

   Indexing output array must use count[...] - 1 because count stores cumulative counts.

2. Step 2: Check other parts

   Counting array size 10 is correct for digits 0-9; prefix sum loop starts at 1; division by exp is correct.

3. Final Answer:

   Indexing output array should be count[...] - 1 -> Option B

4. Quick Check:

   Output index = count - 1 [OK]

Hint: Subtract 1 from count for output indexing [OK]

Common Mistakes:

• Using count directly as index without subtracting 1
• Wrong counting array size
• Incorrect loop start for prefix sums
• Misusing division and modulo operators

5. Given an array of strings representing numbers with leading zeros, e.g., ["002", "010", "001", "100"], how can Radix Sort be adapted to sort them correctly as numbers?

hard

A. Pad all strings to equal length and sort digit by digit from right to left

B. Sort strings lexicographically without changes

C. Convert strings to integers first, then apply Radix Sort

D. Use Radix Sort only on the first character of each string

Solution

1. Step 1: Understand string number sorting

   Strings with leading zeros must be equal length to compare digits correctly.

2. Step 2: Adapt Radix Sort

   Pad strings to same length, then sort digit by digit from right to left to preserve numeric order.

3. Final Answer:

   Pad all strings to equal length and sort digit by digit from right to left -> Option A

4. Quick Check:

   Equal length padding + digit-wise sort = correct numeric order [OK]

Hint: Pad strings to same length before digit-wise sorting [OK]

Common Mistakes:

• Sorting strings lexicographically without padding
• Converting to int loses leading zeros importance
• Sorting only first character causes wrong order