Radix Sort Algorithm in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind Radix Sort Algorithm?

Radix Sort sorts numbers by processing individual digits. It starts from the least significant digit and moves to the most significant digit, grouping numbers by each digit at every step.

beginner

Which data structure is commonly used inside Radix Sort to group numbers by digits?

Queues or buckets are used to group numbers by their current digit during each pass of Radix Sort.

intermediate

Why does Radix Sort work efficiently on fixed-length integers?

Because it processes digits one by one, the number of passes depends on the number of digits, which is fixed for fixed-length integers, making the sorting time predictable and efficient.

intermediate

What is the time complexity of Radix Sort for n numbers with d digits each?

The time complexity is O(d * (n + k)), where n is the number of elements and k is the range of digits (usually 10 for decimal digits).

advanced

Can Radix Sort be used for sorting strings? If yes, how?

Yes, Radix Sort can sort strings by processing characters from the least significant position (rightmost character) to the most significant (leftmost), grouping strings by characters at each position.

What is the first digit Radix Sort processes when sorting numbers?

A Least significant digit

B Most significant digit

C Middle digit

D Random digit

Radix Sort starts sorting from the least significant digit to ensure correct order after all passes.

Which data structure is typically used to hold numbers during each digit grouping in Radix Sort?

A Stack

B Tree

C Queue

D Hash Map

Queues are used to maintain the order of numbers grouped by digits during each pass.

What is the main advantage of Radix Sort over comparison-based sorts like QuickSort?

A It sorts in place

B It has better average case time complexity for fixed digit sizes

C It uses less memory

D It works only on strings

Radix Sort can sort in linear time relative to number of digits and elements, which can be faster than comparison sorts for fixed digit sizes.

What is the time complexity of Radix Sort if n is the number of elements and d is the number of digits?

A O(n log n)

B O(log n)

C O(n^2)

D O(d * n)

Radix Sort runs in O(d * n) time, processing each digit for all elements.

Radix Sort is best suited for which type of data?

A Fixed-length integers or strings

B Floating point numbers

C Linked lists

D Unsorted graphs

Radix Sort works best on fixed-length integers or strings where digits or characters can be processed uniformly.

Explain step-by-step how Radix Sort sorts the array [170, 45, 75, 90, 802, 24, 2, 66].

Think about sorting by units, then tens, then hundreds place.

Describe the difference between Radix Sort and comparison-based sorting algorithms.

Focus on how sorting decisions are made.

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 swapping of elements

2. Which of the following is the correct way to extract the digit at position pos (starting from 0 for least significant digit) from an integer num in C++?

easy

A. (num / (10 * pos)) % 10

B. ((num / (int)pow(10, pos)) % 10)

C. (num % (10 * pos)) / 10

D. (num % pow(10, pos)) / 10

Solution

1. Step 1: Understand digit extraction formula

   To get the digit at position pos, divide num by 10^pos and then take modulo 10.

2. Step 2: Check each option

   ((num / (int)pow(10, pos)) % 10 correctly uses pow(10, pos) for exponentiation and modulo 10 to get the digit.

3. Final Answer:

   ((num / (int)pow(10, pos)) % 10) -> Option B

4. Quick Check:

   Digit extraction = (num / 10^pos) % 10 [OK]

Hint: Divide by 10^pos then mod 10 to get digit [OK]

Common Mistakes:

• Using multiplication instead of exponentiation
• Incorrect order of operations
• Using modulo before division

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

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 = *max_element(arr, arr + n);
    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++)
        cout << arr[i] << " ";
    return 0;
}

medium

A. 24 2 45 66 75 90 170 802

B. 802 170 90 75 66 45 24 2

C. 2 24 45 66 75 90 170 802

D. 2 24 45 75 66 90 170 802

Solution

1. Step 1: Understand Radix Sort steps on given array

   Radix Sort sorts by digits: first units, then tens, then hundreds. After full sorting, array becomes sorted ascending.

2. Step 2: Trace final sorted array

   Sorted array is: 2 24 45 66 75 90 170 802.

3. Final Answer:

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

4. Quick Check:

   Radix Sort final output = sorted array ascending [OK]

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

Common Mistakes:

• Confusing intermediate steps with final output
• Misordering numbers with same digits
• Ignoring stable sorting in countingSort

4. Identify the bug in the following Radix Sort counting sort implementation and select the correct fix:

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 = 0; i < n; 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];
}

medium

A. Change the last for loop to iterate from n-1 down to 0 for stable sorting

B. Initialize count array with -1 instead of 0

C. Remove the cumulative sum loop for count array

D. Replace output array with a vector for dynamic sizing

Solution

1. Step 1: Identify stable sorting requirement in counting sort

   Counting sort must process elements from right to left to maintain stability.

2. Step 2: Check the for loop direction

   Current loop goes from 0 to n-1, which breaks stability. Changing it to n-1 down to 0 fixes this.

3. Final Answer:

   Change the last for loop to iterate from n-1 down to 0 for stable sorting -> Option A

4. Quick Check:

   Stable counting sort = reverse iteration [OK]

Hint: Counting sort must iterate backward for stability [OK]

Common Mistakes:

• Iterating forward breaks stable sorting
• Misunderstanding count array initialization
• Ignoring cumulative sum step

5. Given an array of strings representing numbers with leading zeros, e.g., {"002", "010", "001", "100"}, how can you adapt Radix Sort to correctly sort them as numbers?

hard

A. Use counting sort only on the first character of each string

B. Sort strings lexicographically using Radix Sort on characters

C. Ignore leading zeros and sort strings as-is with Radix Sort

D. Convert strings to integers first, then apply Radix Sort on integers

Solution

1. Step 1: Understand sorting numeric strings with leading zeros

   Sorting strings lexicographically will not sort numbers correctly if leading zeros exist.

2. Step 2: Convert strings to integers for numeric sorting

   Convert strings to integers to remove leading zeros, then apply Radix Sort on integers for correct numeric order.

3. Final Answer:

   Convert strings to integers first, then apply Radix Sort on integers -> Option D

4. Quick Check:

   Numeric string sorting = convert to int then Radix Sort [OK]

Hint: Convert strings to int before Radix Sort for numeric order [OK]

Common Mistakes:

• Sorting strings lexicographically causes wrong order
• Ignoring leading zeros impact
• Using only first character for sorting