Radix Sort Algorithm in DSA C - Deep Dive

Overview - Radix Sort Algorithm

What is it?

Radix Sort is a way to sort numbers by looking at their digits one by one. It starts sorting from the least important digit (like the ones place) and moves to the most important digit (like the thousands place). Instead of comparing numbers directly, it groups them based on each digit. This method works well when sorting many numbers with the same number of digits.

Why it matters

Without Radix Sort, sorting large lists of numbers can be slower because we compare whole numbers repeatedly. Radix Sort speeds this up by sorting digits step-by-step, making it faster for big data sets like phone numbers or IDs. This helps computers organize data quickly, improving apps and systems that rely on fast sorting.

Where it fits

Before learning Radix Sort, you should understand basic sorting methods like Bubble Sort and Counting Sort. After Radix Sort, you can explore more complex sorting algorithms like Quick Sort and Merge Sort, and learn about algorithm efficiency and stability.

Mental Model

Core Idea

Radix Sort sorts numbers by processing each digit from least to most significant, grouping numbers by digits without direct comparisons.

Think of it like...

Imagine sorting mail by zip code: first by the last digit, then the second last, and so on, until all mail is perfectly ordered.

Step 1: Sort by least significant digit (units place)
┌─────────────┐
│ 170  90  802│
│  2   24  45 │
└─────────────┘
Step 2: Sort by next digit (tens place)
┌─────────────┐
│ 802  2  24  │
│ 45  170  90 │
└─────────────┘
Step 3: Sort by most significant digit (hundreds place)
┌─────────────┐
│ 2  24  45   │
│ 90 170 802  │
└─────────────┘

Build-Up - 7 Steps

1

Foundation

Understanding Digits in Numbers

Concept: Numbers have digits in places like ones, tens, hundreds, and each place can be used to sort.

Every number is made of digits. For example, 345 has 3 in hundreds, 4 in tens, and 5 in ones. Radix Sort uses these places to sort numbers step-by-step, starting from the smallest place (ones).

Result

You can identify and separate digits of numbers by their place values.

Understanding digits and their places is key because Radix Sort depends on sorting numbers by each digit separately.

2

Foundation

What is Stable Sorting?

Concept: Stable sorting keeps the order of equal elements the same after sorting.

If two numbers have the same digit in the current place, stable sorting keeps their original order. This is important because Radix Sort relies on stable sorting at each digit step to keep the overall order correct.

Result

Sorting methods like Counting Sort are stable and suitable for Radix Sort.

Knowing stability prevents errors in Radix Sort, ensuring the final list is correctly sorted.

3

Intermediate

Using Counting Sort for Each Digit

🤔Before reading on: Do you think Radix Sort compares whole numbers directly or sorts by digits separately? Commit to your answer.

Concept: Radix Sort uses Counting Sort to sort numbers by each digit without comparing whole numbers.

At each digit place, Radix Sort applies Counting Sort to group numbers by that digit. Counting Sort counts how many times each digit appears and places numbers accordingly, preserving order for equal digits.

Result

Numbers get partially sorted by one digit at a time, moving closer to full order.

Using Counting Sort for digits avoids direct number comparisons, making Radix Sort efficient.

4

Intermediate

Sorting from Least to Most Significant Digit

🤔Before reading on: Should Radix Sort start sorting from the largest digit or the smallest digit? Commit to your answer.

Concept: Radix Sort processes digits starting from the least significant (rightmost) to the most significant (leftmost).

Sorting starts at the ones place, then tens, then hundreds, and so on. This order ensures that after sorting by a more significant digit, the order from previous steps is preserved, thanks to stable sorting.

Result

The list becomes fully sorted after processing all digit places.

Sorting from least to most significant digit ensures the final order is correct and stable.

5

Advanced

Handling Variable Digit Lengths

🤔Before reading on: Do you think Radix Sort can handle numbers with different digit lengths without extra steps? Commit to your answer.

Concept: Radix Sort can handle numbers with different digit lengths by treating missing digits as zero.

When numbers have fewer digits, we consider missing digits as zero during sorting. For example, number 45 is treated as 045 when sorting by hundreds place. This keeps sorting consistent.

Result

Radix Sort correctly sorts numbers even if they have different lengths.

Treating missing digits as zero avoids errors and keeps sorting uniform.

6

Advanced

Time Complexity and Efficiency

🤔Before reading on: Is Radix Sort always faster than comparison-based sorts like Quick Sort? Commit to your answer.

Concept: Radix Sort runs in linear time relative to the number of digits and elements, but depends on digit size and stability.

Radix Sort's time is O(d*(n+k)) where d is digit count, n is number of elements, and k is digit range (usually 10). For large n and small d, it's faster than comparison sorts (O(n log n)). But for large digit counts, it can be slower.

Result

Radix Sort is efficient for fixed digit-length data like IDs or phone numbers.

Knowing when Radix Sort is efficient helps choose the right sorting method for the problem.

7

Expert

Memory Use and In-Place Sorting Challenges

🤔Before reading on: Do you think Radix Sort sorts numbers in-place without extra memory? Commit to your answer.

Concept: Radix Sort usually requires extra memory for Counting Sort buckets, making in-place sorting difficult.

Because Counting Sort needs temporary arrays to count and place elements, Radix Sort uses extra space proportional to input size. In-place Radix Sort versions exist but are complex and less common in practice.

Result

Radix Sort trades memory for speed, which can be a limitation in memory-constrained environments.

Understanding memory tradeoffs guides practical use and optimization of Radix Sort.

Under the Hood

Radix Sort works by repeatedly grouping numbers based on each digit, starting from the least significant digit. At each step, it uses a stable sorting method (usually Counting Sort) to order numbers by the current digit. This stability ensures that the order from previous digit sorts is preserved. Internally, Counting Sort counts occurrences of each digit, calculates positions, and rearranges numbers accordingly. This process repeats for all digit places until the entire list is sorted.

Why designed this way?

Radix Sort was designed to avoid direct comparisons between whole numbers, which can be costly. By breaking numbers into digits and sorting stepwise, it leverages Counting Sort's linear time for small ranges (digits 0-9). This design trades extra memory for speed and stability. Alternatives like comparison sorts were slower for large datasets with fixed digit lengths. The digit-by-digit approach also aligns well with hardware and data representations.

Input List
  ↓
Extract Digit (Least Significant)
  ↓
Counting Sort by Digit
  ↓
Stable Partial Sort
  ↓
Extract Next Digit
  ↓
Counting Sort by Digit
  ↓
Repeat Until Most Significant Digit
  ↓
Fully Sorted List

Myth Busters - 4 Common Misconceptions

Quick: Does Radix Sort compare whole numbers directly? Commit to yes or no.

Common Belief: Radix Sort compares whole numbers directly like Quick Sort or Merge Sort.

Reality: Radix Sort never compares whole numbers directly; it sorts numbers digit by digit using stable sorting.

Why it matters: Believing this leads to misunderstanding Radix Sort's efficiency and when to use it.

Quick: Is Radix Sort always faster than all other sorting algorithms? Commit to yes or no.

Common Belief: Radix Sort is always the fastest sorting algorithm regardless of data.

Reality: Radix Sort is faster only when digit count is small and data fits its assumptions; otherwise, comparison sorts can be faster.

Why it matters: Overusing Radix Sort on unsuitable data wastes resources and slows programs.

Quick: Can Radix Sort sort negative numbers without changes? Commit to yes or no.

Common Belief: Radix Sort can sort negative and positive numbers without any modification.

Reality: Radix Sort needs special handling for negative numbers, often by separating negatives and positives or adjusting digit extraction.

Why it matters: Ignoring this causes incorrect sorting results with mixed sign numbers.

Quick: Does Radix Sort sort in-place without extra memory? Commit to yes or no.

Common Belief: Radix Sort sorts the list in-place without needing extra memory.

Reality: Radix Sort requires extra memory for counting and temporary arrays during sorting steps.

Why it matters: Assuming in-place sorting can cause memory errors or inefficient implementations.

Expert Zone

1

Radix Sort's performance depends heavily on digit extraction efficiency; optimizing this can speed up sorting significantly.

2

Stable sorting at each digit step is critical; using unstable sorts breaks the algorithm's correctness.

3

Memory usage can be optimized by reusing counting arrays and careful buffer management, important in large-scale systems.

When NOT to use

Avoid Radix Sort when sorting data with very large digit counts or non-integer data types. Use comparison-based sorts like Quick Sort or Merge Sort for general-purpose sorting or when memory is limited.

Production Patterns

Radix Sort is commonly used in systems sorting fixed-length numeric keys like phone numbers, IP addresses, or database indexing. It is also used in parallel processing where digit-based partitioning allows distributed sorting.

Connections

Counting Sort

Radix Sort builds on Counting Sort as its stable sorting step for each digit.

Understanding Counting Sort's stability and linear time is essential to grasp why Radix Sort is efficient.

Bucket Sort

Radix Sort is related to Bucket Sort as both distribute elements into groups based on parts of their value.

Knowing Bucket Sort helps understand how Radix Sort partitions data by digits.

Human Sorting of Postal Mail

Radix Sort mimics the real-world process of sorting mail by zip code digits from right to left.

Recognizing this connection shows how algorithms can model everyday organizational tasks.

Common Pitfalls

#1 Sorting digits from most significant to least significant.

Wrong approach:

for (int digit = maxDigit; digit >= 0; digit--) {
countingSortByDigit(arr, digit);
}

Correct approach:

for (int digit = 0; digit <= maxDigit; digit++) {
countingSortByDigit(arr, digit);
}

Root cause:

Misunderstanding the importance of sorting from least significant digit first to preserve stability.

#2 Using an unstable sort for digit sorting steps.

Wrong approach:

Using Quick Sort to sort numbers by digit without stability guarantees.

Correct approach:

Using Counting Sort which is stable for sorting by each digit.

Root cause:

Not realizing that stability is required to maintain correct order across digit passes.

#3 Ignoring numbers with different digit lengths.

Wrong approach:

Not padding shorter numbers or treating missing digits as zero during sorting.

Correct approach:

Treat missing digits as zero to ensure consistent sorting across all numbers.

Root cause:

Assuming all numbers have the same number of digits without handling shorter ones.

Key Takeaways

Radix Sort sorts numbers by processing digits from least to most significant using stable sorting at each step.

Stability in sorting is crucial to maintain the correct order when sorting digit by digit.

Radix Sort is efficient for fixed-length numeric data but requires extra memory and careful digit handling.

It is not a general-purpose sort and should be chosen based on data characteristics and performance needs.

Understanding Radix Sort deepens knowledge of sorting algorithms and their tradeoffs in speed, memory, and complexity.

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