Radix Sort Algorithm in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is Radix Sort?

Radix Sort is a sorting method that sorts numbers digit by digit, starting from the least significant digit to the most significant digit, using counting sort as a subroutine.

beginner

Why does Radix Sort work well for sorting integers?

Because it sorts numbers based on individual digits, it can sort integers efficiently without comparing whole numbers directly, making it faster for large lists of numbers with fixed digit lengths.

intermediate

What is the role of Counting Sort in Radix Sort?

Counting Sort is used as a stable sorting method to sort the numbers based on each digit during each pass of Radix Sort, ensuring the relative order of digits is maintained.

intermediate

What is the time complexity of Radix Sort?

The time complexity is O(d*(n + k)) where d is the number of digits, n is the number of elements, and k is the range of digits (usually 10 for decimal digits).

advanced

Can Radix Sort be used for sorting strings? If yes, how?

Yes, Radix Sort can sort strings by processing characters from the least significant position (rightmost character) to the most significant (leftmost), using a stable sort at each step.

What is the first digit position Radix Sort processes?

A Most significant digit (leftmost)

B Least significant digit (rightmost)

C Middle digit

D Random digit

Radix Sort starts sorting from the least significant digit to ensure stable sorting of digits.

Which sorting algorithm is commonly used inside Radix Sort for sorting digits?

A Counting Sort

B Bubble Sort

C Quick Sort

D Merge Sort

Counting Sort is used because it is stable and efficient for sorting digits with a small range.

What is the main advantage of Radix Sort over comparison-based sorts?

A It uses less memory

B It works only on strings

C It sorts in linear time for fixed digit lengths

D It is easier to implement

Radix Sort can sort in linear time O(n) when the number of digits is fixed, unlike comparison sorts which are O(n log n).

What does it mean that Counting Sort used in Radix Sort is stable?

A It sorts numbers in ascending order

B It sorts in place

C It uses constant extra space

D It keeps the relative order of equal elements

Stability means that elements with the same digit keep their original order after sorting.

If you have numbers with 4 digits, how many passes does Radix Sort perform?

A 4

B 2

C 1

D 3

Radix Sort performs one pass per digit, so 4 digits mean 4 passes.

Explain how Radix Sort sorts a list of numbers step-by-step.

Think about sorting by each digit from right to left.

Describe why stability in the sorting method used inside Radix Sort is important.

Consider what happens if order changes after sorting a digit.

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