Radix Sort Algorithm in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Radix Sort on a small array

What is the output of the following Radix Sort implementation on the array [170, 45, 75, 90, 802, 24, 2, 66]?

DSA C

void radixSort(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
    }
    for (int exp = 1; max / exp > 0; exp *= 10) {
        int output[n];
        int count[10] = {0};
        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--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }
        for (int i = 0; i < n; i++)
            arr[i] = output[i];
    }
}

int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);
    radixSort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

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

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

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

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

💡 Hint

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

Radix sort processes digits from right to left. After sorting by each digit, the array becomes more sorted. The final sorted array is in ascending order.

🧠 Conceptual

intermediate

Understanding Radix Sort Stability

Why is it important that the sorting algorithm used at each digit level in Radix Sort is stable?

A Because stability makes the algorithm faster by skipping unnecessary comparisons.

B Because stability reduces the memory usage of the algorithm.

C Because stability allows sorting negative numbers directly without extra steps.

D Because stability ensures that the relative order of elements with the same digit remains unchanged, preserving previous digit sorting.

💡 Hint

Think about what happens when sorting by multiple digits one after another.

Radix sort sorts digits from least significant to most significant. If the sorting at each digit is stable, the order of elements sorted by previous digits is preserved, ensuring correct final order.

🔧 Debug

advanced

Identify the bug in this Radix Sort code snippet

What error will this Radix Sort code produce when sorting the array [3, 1, 2]?

DSA C

void radixSort(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
    }
    for (int exp = 1; max / exp > 0; exp *= 10) {
        int output[n];
        int count[10];
        for (int i = 0; i < 10; i++)
            count[i] = 0;
        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--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }
        for (int i = 0; i < n; i++)
            arr[i] = output[i];
    }
}

int main() {
    int arr[] = {3, 1, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    radixSort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

A No error, outputs: 1 2 3

B Runtime error due to uninitialized count array

C Syntax error: missing initialization of count array

D Wrong output: 3 2 1

💡 Hint

Check how the count array is initialized before counting digits.

The count array is initialized with a loop setting all elements to zero before use, so no runtime or syntax error occurs. The output is correctly sorted.

❓ Predict Output

advanced

Output of Radix Sort with numbers having different digit lengths

What is the output of Radix Sort on the array [5, 123, 9, 45, 1000]?

DSA C

void radixSort(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
    }
    for (int exp = 1; max / exp > 0; exp *= 10) {
        int output[n];
        int count[10] = {0};
        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--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }
        for (int i = 0; i < n; i++)
            arr[i] = output[i];
    }
}

int main() {
    int arr[] = {5, 123, 9, 45, 1000};
    int n = sizeof(arr) / sizeof(arr[0]);
    radixSort(arr, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

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

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

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

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

💡 Hint

Radix sort sorts numbers by each digit starting from the least significant digit, handling different digit lengths correctly.

Radix sort sorts numbers digit by digit. Numbers with fewer digits are treated as having leading zeros. The final sorted array is ascending.

🧠 Conceptual

expert

Radix Sort Time Complexity Analysis

Given an array of n integers where the maximum number has d digits, what is the time complexity of Radix Sort and why?

A O(d * (n + k)) where k is the base of the number system, because it sorts digits one by one using counting sort.

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

C O(n^2) because it sorts each digit with nested loops.

D O(d * n^2) because it sorts digits and elements in quadratic time.

💡 Hint

Consider how many passes and what sorting method is used at each digit.

Radix sort performs d passes over the array, each pass using counting sort which runs in O(n + k) time, where k is the digit range (usually 10). So total time is O(d * (n + k)).

Practice

1. What is the main idea behind the Radix Sort Algorithm?

easy

A. Divide the array into halves and sort each half recursively

B. Compare each element with every other element and swap if needed

C. Sort numbers digit by digit starting from the least significant digit

D. Use a pivot to partition the array and sort partitions separately

Solution

1. Step 1: Understand Radix Sort process

   Radix Sort sorts numbers by processing each digit from least significant to most significant.

2. Step 2: Compare with other sorting methods

   Unlike comparison-based sorts, Radix Sort uses digit positions to sort without direct comparisons.

3. Final Answer:

   Sort numbers digit by digit starting from the least significant digit -> Option C

4. Quick Check:

   Radix Sort = Digit by digit sorting [OK]

Hint: Remember: Radix Sort sorts 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 recursion

2. Which of the following is the correct way to initialize the counting array for Radix Sort in C?

easy

A. int count[10] = {0};

B. int count[10]; // no initialization

C. int count[10] = {1};

D. int count[10] = NULL;

Solution

1. Step 1: Understand counting array role

   The counting array stores frequency of digits 0-9 and must start at zero.

2. Step 2: Check initialization options

   Only int count[10] = {0}; sets all elements to zero correctly in C.

3. Final Answer:

   int count[10] = {0}; -> Option A

4. Quick Check:

   Counting array must start with zeros [OK]

Hint: Initialize counting array with zeros using {0} [OK]

Common Mistakes:

• Leaving counting array uninitialized
• Initializing with all ones
• Assigning NULL to an int array

3. What is the output of the following C code snippet using Radix Sort on array arr = {170, 45, 75, 90, 802, 24, 2, 66}?

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr)/sizeof(arr[0]);
    radixSort(arr, n); // Assume radixSort is correctly implemented
    printArray(arr, n);
    return 0;
}

medium

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

Solution

1. Step 1: Understand Radix Sort output

   Radix Sort sorts the array fully in ascending order after processing all digits.

2. Step 2: Sort given array

   Sorted array is [2, 24, 45, 66, 75, 90, 170, 802].

3. Final Answer:

   2 24 45 66 75 90 170 802 -> Option D

4. Quick Check:

   Sorted array matches 2 24 45 66 75 90 170 802 [OK]

Hint: Radix Sort outputs fully sorted array ascending [OK]

Common Mistakes:

• Assuming output is unchanged
• Thinking output is reversed
• Confusing partial digit sorting with final output

4. Identify the error in this Radix Sort counting step code snippet:

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

medium

A. Counting array size should be 100, not 10

B. Indexing output array should be count[...] - 1

C. Loop for count prefix sum should start from 0

D. Division by exp should be replaced by modulo exp

Solution

1. Step 1: Analyze output array indexing

   Indexing output array must use count[...] - 1 because count stores cumulative counts.

2. Step 2: Check other parts

   Counting array size 10 is correct for digits 0-9; prefix sum loop starts at 1; division by exp is correct.

3. Final Answer:

   Indexing output array should be count[...] - 1 -> Option B

4. Quick Check:

   Output index = count - 1 [OK]

Hint: Subtract 1 from count for output indexing [OK]

Common Mistakes:

• Using count directly as index without subtracting 1
• Wrong counting array size
• Incorrect loop start for prefix sums
• Misusing division and modulo operators

5. Given an array of strings representing numbers with leading zeros, e.g., ["002", "010", "001", "100"], how can Radix Sort be adapted to sort them correctly as numbers?

hard

A. Pad all strings to equal length and sort digit by digit from right to left

B. Sort strings lexicographically without changes

C. Convert strings to integers first, then apply Radix Sort

D. Use Radix Sort only on the first character of each string

Solution

1. Step 1: Understand string number sorting

   Strings with leading zeros must be equal length to compare digits correctly.

2. Step 2: Adapt Radix Sort

   Pad strings to same length, then sort digit by digit from right to left to preserve numeric order.

3. Final Answer:

   Pad all strings to equal length and sort digit by digit from right to left -> Option A

4. Quick Check:

   Equal length padding + digit-wise sort = correct numeric order [OK]

Hint: Pad strings to same length before digit-wise sorting [OK]

Common Mistakes:

• Sorting strings lexicographically without padding
• Converting to int loses leading zeros importance
• Sorting only first character causes wrong order