Radix Sort Algorithm in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Radix Sort on a small array

What is the output of the following Java code after applying Radix Sort on the array?

DSA Java

import java.util.*;

public class RadixSortExample {
    public static void radixSort(int[] arr) {
        int max = Arrays.stream(arr).max().getAsInt();
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSortByDigit(arr, exp);
        }
    }

    private static void countingSortByDigit(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10];

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

        System.arraycopy(output, 0, arr, 0, n);
    }

    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
        radixSort(arr);
        System.out.print(Arrays.toString(arr));
    }
}

A [2, 24, 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, 75, 66, 90, 170, 802]

💡 Hint

Radix sort sorts numbers digit by digit starting from the least significant digit.

Radix sort processes digits from least significant to most significant using counting sort as a subroutine. The final sorted array is in ascending order.

🧠 Conceptual

intermediate

Understanding Radix Sort Stability

Why is stability important in Radix Sort?

A Because it ensures that numbers with the same digit keep their original order, preserving previous sorting by less significant digits.

B Because it allows Radix Sort to sort negative numbers directly without extra steps.

C Because it reduces the time complexity from O(n log n) to O(n).

D Because it uses less memory than unstable sorting algorithms.

💡 Hint

Think about how sorting digit by digit works and why order preservation matters.

Radix Sort sorts digits starting from the least significant digit. Stability ensures that when sorting by a more significant digit, the order of numbers with the same digit remains as sorted by previous digits.

🔧 Debug

advanced

Identify the bug in this Radix Sort implementation

What error will this Java code produce when run?

DSA Java

public class RadixSortBug {
    public static void radixSort(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) max = arr[i];
        }
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSortByDigit(arr, exp);
        }
    }

    private static void countingSortByDigit(int[] arr, int exp) {
        // Implementation omitted for brevity
    }
}

A ArithmeticException

B NullPointerException

C No error, runs correctly

D ArrayIndexOutOfBoundsException

💡 Hint

Check the loop condition carefully when iterating over array indices.

The loop uses i <= arr.length which tries to access arr[arr.length], causing ArrayIndexOutOfBoundsException.

❓ Predict Output

advanced

Radix Sort output with numbers having different digit lengths

What is the output of this Java code after applying Radix Sort on the array?

DSA Java

import java.util.*;

public class RadixSortTest {
    public static void radixSort(int[] arr) {
        int max = Arrays.stream(arr).max().getAsInt();
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSortByDigit(arr, exp);
        }
    }

    private static void countingSortByDigit(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10];

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

        System.arraycopy(output, 0, arr, 0, n);
    }

    public static void main(String[] args) {
        int[] arr = {5, 123, 9, 45, 1000, 56};
        radixSort(arr);
        System.out.print(Arrays.toString(arr));
    }
}

A [1000, 123, 56, 45, 9, 5]

B [5, 9, 56, 45, 123, 1000]

C [5, 9, 45, 56, 123, 1000]

D [9, 5, 45, 56, 123, 1000]

💡 Hint

Radix sort handles numbers with different digit lengths by treating missing digits as zero.

Radix sort sorts numbers digit by digit from least significant to most significant. The final sorted array is ascending.

🧠 Conceptual

expert

Radix Sort Time Complexity Analysis

What is the time complexity of Radix Sort for sorting n numbers with d digits each, assuming counting sort is used as the stable sorting subroutine?

A O(n^2) due to repeated sorting of digits

B O(d * (n + k)) where k is the range of digits (usually 10)

C O(n log n) because it uses comparison-based sorting internally

D O(d * n^2) because counting sort is applied d times

💡 Hint

Counting sort runs in O(n + k) and is applied d times.

Radix sort applies counting sort d times, each taking O(n + k) time. Since k (digit range) is constant (10), complexity is O(d * n).

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