Radix Sort Algorithm in DSA Java - 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 digits from least to most significant, grouping numbers by each digit and collecting them repeatedly until sorted.

Execution Sample

DSA Java

int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
radixSort(arr);
// Sorts array by digits from LSD to MSD

Sorts the array by grouping numbers by each digit starting from the least significant digit.

Execution Table

Step	Operation	Digit Place	Buckets (0-9)	Array After Collection	Visual State
1	Find max number	-	-	-	Max number is 802, max digits = 3
2	Sort by digit 1 (units)	1	[170, 90], [], [802, 2], [], [24], [45, 75], [66], [], [], []	[170, 90, 802, 2, 24, 45, 75, 66]	Buckets: 0:[170, 90],1:[],2:[802, 2],3:[],4:[24],5:[45, 75],6:[66],7:[],8:[],9:[]
3	Sort by digit 2 (tens)	10	[802, 2], [], [24], [], [45], [], [66], [170, 75], [], [90]	[802, 2, 24, 45, 66, 170, 75, 90]	Buckets: 0:[802, 2],1:[],2:[24],3:[],4:[45],5:[],6:[66],7:[170, 75],8:[],9:[90]
4	Sort by digit 3 (hundreds)	100	[2, 24, 45, 66, 75, 90], [170], [], [], [], [], [], [], [802], []	[2, 24, 45, 66, 75, 90, 170, 802]	Buckets: 0:[2, 24, 45, 66, 75, 90],1:[170],2:[],3:[],4:[],5:[],6:[],7:[],8:[802],9:[]
5	All digits processed	-	-	[2, 24, 45, 66, 75, 90, 170, 802]	Sorted array ready

💡 All digits processed (max digits = 3), array is sorted

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
arr	[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	802	802	802	802	802
digitPlace	-	1	10	100	-

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 level, starting from the least significant digit ensures that the order of previous digits is preserved, as shown in execution_table rows 2 and 3.

What happens if numbers have different digit lengths?

Shorter numbers are treated as having 0 in the missing higher digit places, so they go into bucket 0 for those digits, as seen in step 4 where numbers like 2 and 24 are in bucket 0.

Why do we need to find the maximum number first?

To know how many digits we must process. The max number 802 has 3 digits, so we repeat the sorting process 3 times (execution_table step 1).

Visual Quiz - 3 Questions

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

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

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

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

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

💡 Hint

Check the 'Array After Collection' column for step 3 in execution_table

At which step does the digitPlace variable become 100?

A After Step 4

B After Step 3

C After Step 2

D After Step 5

💡 Hint

Look at variable_tracker row for digitPlace and see when it changes to 100

If the maximum number was 99 instead of 802, how many times would the sorting loop run?

A 1 time

B 2 times

C 3 times

D 4 times

💡 Hint

Max digits depend on the number of digits in the max number, see execution_table step 1

Concept Snapshot

Radix Sort Algorithm
- Sorts numbers digit by digit from least to most significant
- Uses buckets (0-9) to group numbers by current digit
- Collects numbers from buckets after each digit pass
- Repeats for max digits in the largest number
- Stable sorting at each digit ensures overall sorted order

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 (units, tens, hundreds, etc.), it places numbers into buckets based on the current digit. After placing, it collects numbers from the buckets in order to form a new array. This process repeats for each digit place until all digits are processed. The array becomes sorted at the end. This method relies on stable sorting at each digit to maintain order from previous steps.

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 pivot or divide and conquer

2. Which of the following is the correct way to get the digit at position pos (starting from 0 for least significant digit) of a number num in Java?

easy

A. (num % (int) Math.pow(10, pos)) / 10

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

C. (num * (int) Math.pow(10, pos)) % 10

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

Solution

1. Step 1: Understand digit extraction logic

   To get the digit at position pos, divide num by 10^pos to shift digits right, then take modulo 10 to get the last digit.

2. Step 2: Check each option

   (num / (int) Math.pow(10, pos)) % 10 correctly divides num by 10^pos and then modulo 10. Others do incorrect operations.

3. Final Answer:

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

4. Quick Check:

   Digit extraction = divide then modulo [OK]

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

Common Mistakes:

• Using modulo before division
• Multiplying instead of dividing
• Incorrect order of operations

3. What will be the output array after one pass of Radix Sort on the array [170, 45, 75, 90, 802] sorting by the least significant digit (units place)?

medium

A. [45, 75, 90, 170, 802]

B. [802, 170, 90, 45, 75]

C. [170, 90, 802, 45, 75]

D. [75, 45, 170, 90, 802]

Solution

1. Step 1: Extract least significant digit of each number

   170 -> 0, 45 -> 5, 75 -> 5, 90 -> 0, 802 -> 2

2. Step 2: Sort array by these digits

   Order by digits: 0s first (170, 90), then 2 (802), then 5s (45, 75). So array becomes [170, 90, 802, 45, 75]

3. Final Answer:

   [170, 90, 802, 45, 75] -> Option C

4. Quick Check:

   Sort by units digit = [170, 90, 802, 45, 75] [OK]

Hint: Sort by digit at current place only [OK]

Common Mistakes:

• Sorting entire numbers instead of digits
• Mixing digit positions
• Ignoring stable sorting requirement

4. Consider this Java code snippet for Radix Sort digit extraction:

int digit = (num % (int) Math.pow(10, pos)) / (int) Math.pow(10, pos - 1);

What is the error in this code?

medium

A. No error, code works correctly

B. Incorrect order of modulo and division operations

C. Casting to int causes loss of precision

D. Division by zero when pos = 0

Solution

1. Step 1: Analyze division when pos = 0

   When pos = 0, expression divides by Math.pow(10, -1), which is 10^-1 = 0.1, but casting to int makes it 0, causing division by zero error.

2. Step 2: Check other options

   Modulo and division order is correct for digit extraction, casting is intentional, so no other errors.

3. Final Answer:

   Division by zero when pos = 0 -> Option D

4. Quick Check:

   pos=0 causes division by zero [OK]

Hint: Check division by zero for edge digit positions [OK]

Common Mistakes:

• Ignoring pos=0 edge case
• Assuming casting fixes division issues
• Thinking modulo order is wrong

5. Given the array [329, 457, 657, 839, 436, 720, 355], how many passes (iterations over digits) will Radix Sort perform to fully sort this array?

hard

A. 3 passes

B. 4 passes

C. 2 passes

D. 1 pass

Solution

1. Step 1: Find the maximum number of digits in the array

   The largest number is 839, which has 3 digits.

2. Step 2: Determine passes needed

   Radix Sort performs one pass per digit, so 3 passes are needed (units, tens, hundreds).

3. Final Answer:

   3 passes -> Option A

4. Quick Check:

   Max digits = 3, passes = 3 [OK]

Hint: Passes = number of digits in largest number [OK]

Common Mistakes:

• Counting array length instead of digit count
• Assuming fixed number of passes
• Ignoring leading zeros in numbers