Why Radix Sort Algorithm in DSA C++?

The Big Idea

What if you could sort thousands of numbers without comparing them directly, just by looking at their digits one by one?

The Scenario

Imagine you have a huge stack of mail envelopes with different zip codes, and you need to sort them by their numbers. Doing it by hand, comparing each number fully, would take forever and be very tiring.

The Problem

Sorting numbers by comparing them one by one is slow and confusing when the list is very long. It's easy to make mistakes and takes a lot of time because you look at the whole number each time.

The Solution

Radix Sort looks at numbers digit by digit, starting from the smallest place (like the ones place) and moving to the largest. This way, it sorts numbers quickly and in an organized way without comparing whole numbers directly.

Before vs After

✗ Before

for (int i = 0; i < n-1; i++) {
  for (int j = 0; j < n-i-1; j++) {
    if (arr[j] > arr[j+1]) swap(arr[j], arr[j+1]);
  }
}

✓ After

for (int exp = 1; maxNum / exp > 0; exp *= 10) {
  countingSortByDigit(arr, n, exp);
}

What It Enables

It enables fast sorting of large lists of numbers by breaking the problem into simple steps based on digits.

Real Life Example

Sorting phone numbers or social security numbers quickly in a database without comparing entire numbers each time.

Key Takeaways

Manual full-number comparisons are slow and error-prone.

Radix Sort sorts numbers digit by digit for speed and simplicity.

This method is great for sorting large lists of numbers efficiently.

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