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 C++ code after applying Radix Sort on the array?

DSA C++

void countingSort(int arr[], int n, int exp) {
    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];
}

void radixSort(int arr[], int n) {
    int maxVal = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > maxVal) maxVal = arr[i];
    for (int exp = 1; maxVal / exp > 0; exp *= 10)
        countingSort(arr, n, exp);
}

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++)
        std::cout << arr[i] << " ";
    return 0;
}

A 802 170 90 75 66 45 24 2

B 2 24 45 66 75 90 170 802

C 2 24 45 66 75 170 90 802

D 170 45 75 90 802 24 2 66

💡 Hint

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

Radix sort uses counting sort on each digit starting from the least significant digit. After sorting all digits, the array becomes sorted in ascending order.

❓ Predict Output

intermediate

Radix Sort output with numbers having different digit lengths

What will be the output of the following code after applying Radix Sort on the array?

DSA C++

int arr[] = {3, 300, 34, 5, 9};
int n = sizeof(arr) / sizeof(arr[0]);
radixSort(arr, n);
for (int i = 0; i < n; i++)
    std::cout << arr[i] << " ";

A 3 5 9 34 300

B 300 34 9 5 3

C 3 34 5 9 300

D 5 3 9 34 300

💡 Hint

Radix sort handles numbers with different digit lengths by sorting from least significant digit.

Radix sort sorts numbers digit by digit. Smaller numbers with fewer digits come before larger numbers when sorted correctly.

🧠 Conceptual

advanced

Why Radix Sort is not comparison-based?

Which statement best explains why Radix Sort is not a comparison-based sorting algorithm?

A It sorts numbers by grouping digits and using counting sort without direct element comparisons.

B It sorts numbers by comparing each pair of elements multiple times.

C It uses quicksort internally to sort digits of numbers.

D It compares elements only once and then sorts them using a heap.

💡 Hint

Think about how Radix Sort processes digits instead of comparing whole numbers.

Radix Sort processes digits of numbers and uses counting sort on each digit, which does not involve comparing elements directly.

🔧 Debug

advanced

Identify the bug in this Radix Sort counting sort implementation

What error will this code cause when running countingSort in Radix Sort?

DSA C++

void countingSort(int arr[], int n, int exp) {
    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];
}

A Logical error causing reversed sorted array

B No error, code runs correctly

C Compilation error due to missing semicolon

D Array index out of bounds error due to incorrect loop limit in count array update

💡 Hint

Check the loop that updates the count array prefix sums.

The loop runs from i=1 to i<=10, but count array has size 10 (indices 0 to 9). Accessing count[10] causes out of bounds error.

🚀 Application

expert

Radix Sort on strings of digits

Given an array of strings representing numbers with equal length digits, which approach correctly sorts them using Radix Sort?

A Sort strings from leftmost character to rightmost using counting sort on each character

B Sort strings lexicographically using built-in sort only

C Sort strings from rightmost character to leftmost using counting sort on each character

D Convert strings to integers and apply quicksort

💡 Hint

Radix Sort processes digits starting from least significant digit.

Radix Sort on strings representing numbers sorts from rightmost character (least significant digit) to leftmost using counting sort at each step.