Radix Sort Algorithm in DSA Java - Build from Scratch

Radix Sort Algorithm

📖 Scenario: You work in a warehouse where packages are labeled with numbers. You want to sort these package numbers quickly to organize shipments.

🎯 Goal: Build a Java program that sorts an array of package numbers using the Radix Sort algorithm.

📋 What You'll Learn

Create an integer array called packages with the exact values: 170, 45, 75, 90, 802, 24, 2, 66

Create an integer variable called maxNumber to store the maximum value in packages

Implement the Radix Sort logic using a while loop and a helper method countingSortByDigit

Print the sorted packages array as space-separated values

💡 Why This Matters

🌍 Real World

Sorting package numbers quickly helps warehouses organize shipments efficiently and avoid delays.

💼 Career

Understanding Radix Sort is useful for software engineers working on performance-critical sorting tasks and large data processing.

1

Create the initial array of package numbers

Create an integer array called packages with these exact values: 170, 45, 75, 90, 802, 24, 2, 66

DSA Java

// Create the integer array packages with the given values
// Your code here

Hint

Use int[] packages = {170, 45, 75, 90, 802, 24, 2, 66}; to create the array.

2

Find the maximum number in the array

Create an integer variable called maxNumber and set it to the maximum value in the packages array using a for loop

DSA Java

int[] packages = {170, 45, 75, 90, 802, 24, 2, 66};
// Find the maximum number in packages and store it in maxNumber
// Your code here

Hint

Start with maxNumber = packages[0] and update it inside a for loop.

3

Implement Radix Sort core logic

Write a while loop that runs while maxNumber / exp > 0, where exp starts at 1 and multiplies by 10 each iteration. Inside the loop, call a method countingSortByDigit(packages, exp) to sort by the current digit. Also, implement the countingSortByDigit method that sorts the array by the digit at exp place.

DSA Java

int[] packages = {170, 45, 75, 90, 802, 24, 2, 66};
int maxNumber = packages[0];
for (int i = 1; i  maxNumber) {
        maxNumber = packages[i];
    }
}

// Implement Radix Sort using countingSortByDigit
// Your code here

// Implement countingSortByDigit method below
// Your code here

Hint

Use a while loop with exp starting at 1 and multiply by 10 each time. Implement countingSortByDigit to sort by digit.

4

Print the sorted array

Print the elements of the packages array separated by spaces using a for loop

DSA Java

Hint

Use a for loop to print each element of packages followed by a space.

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