Why Radix Sort Algorithm in DSA Java?

The Big Idea

What if you could sort thousands of numbers without comparing them directly, just by looking at their digits?

The Scenario

Imagine you have a huge stack of mail envelopes with different zip codes, and you need to sort them by zip code to deliver them efficiently.

Doing this by looking at each zip code digit by digit manually would take forever and be very confusing.

The Problem

Sorting these envelopes by comparing whole zip codes one by one is slow and tiring.

It's easy to make mistakes, especially when zip codes are long or many.

Manual sorting also wastes time because you have to compare every pair repeatedly.

The Solution

Radix Sort solves this by sorting the zip codes digit by digit, starting from the least important digit to the most important.

This way, it groups envelopes quickly without comparing whole numbers directly.

It's like sorting mail by the last digit first, then the second last, and so on, making the process fast and organized.

Before vs After

✗ Before

for (int i = 0; i < array.length; i++) {
  for (int j = i + 1; j < array.length; j++) {
    if (array[i] > array[j]) {
      int temp = array[i];
      array[i] = array[j];
      array[j] = temp;
    }
  }
}

✓ After

for (int digit = 1; max / digit > 0; digit *= 10) {
  countingSortByDigit(array, digit);
}

What It Enables

Radix Sort enables fast sorting of large lists of numbers by breaking the problem into simple digit-based steps.

Real Life Example

Sorting phone numbers in a contact list quickly so you can find any number without delay.

Key Takeaways

Manual sorting by full numbers is slow and error-prone.

Radix Sort sorts numbers digit by digit for speed and simplicity.

This method is great for sorting large sets of numbers like zip codes or phone numbers.

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