Radix Sort Algorithm in DSA C

Mental Model

Radix sort sorts numbers by processing digits from least to most significant, grouping numbers by each digit step by step.

Analogy: Imagine sorting mail by zip code: first by the last digit, then the second last, and so on, until fully sorted.

Array: [170, 45, 75, 90, 802, 24, 2, 66]
Buckets for digit 0-9:
0: []
1: []
2: []
3: []
4: []
5: []
6: []
7: []
8: []
9: []

Dry Run Walkthrough

Input: list: [170, 45, 75, 90, 802, 24, 2, 66]

Goal: Sort the list in ascending order using radix sort

Step 1: Sort numbers by least significant digit (units place)

Buckets:
0: [170, 90]
1: []
2: [802, 2]
3: []
4: [24]
5: [45, 75]
6: [66]
7: []
8: []
9: []
Reassembled array: [170, 90, 802, 2, 24, 45, 75, 66]

Why: Grouping by units digit organizes numbers partially towards sorted order

Step 2: Sort numbers by second least significant digit (tens place)

Buckets:
0: [802, 2]
1: []
2: [24]
3: []
4: [45]
5: []
6: [66]
7: [170, 75]
8: []
9: [90]
Reassembled array: [802, 2, 24, 45, 66, 170, 75, 90]

Why: Sorting by tens digit refines order further

Step 3: Sort numbers by third least significant digit (hundreds place)

Buckets:
0: [2, 24, 45, 66, 75, 90]
1: [170]
2: []
3: []
4: []
5: []
6: []
7: []
8: [802]
9: []
Reassembled array: [2, 24, 45, 66, 75, 90, 170, 802]

Why: Sorting by hundreds digit completes the sorting process

Result:

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

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Function to get maximum value in array
int getMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

// Counting sort based on digit represented by exp
void countingSort(int arr[], int n, int exp) {
    int output[n];
    int count[10] = {0};

    // Count occurrences of digits
    for (int i = 0; i < n; i++) {
        int digit = (arr[i] / exp) % 10;
        count[digit]++;
    }

    // Change count[i] so it contains actual position
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    // Build output array from right to left to keep stable sort
    for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }

    // Copy output to arr
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// Main radix sort function
void radixSort(int arr[], int n) {
    if (n == 0) return; // Handle empty array gracefully
    int max = getMax(arr, n);

    // Sort by each digit from least to most significant
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSort(arr, n, exp);
    }
}

// Print array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d", arr[i]);
        if (i < n - 1) printf(" -> ");
    }
    printf(" -> null\n");
}

int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array:\n");
    printArray(arr, n);

    radixSort(arr, n);

    printf("Sorted array:\n");
    printArray(arr, n);

    return 0;
}

for (int i = 1; i < n; i++) { if (arr[i] > max) { max = arr[i]; } }

Find maximum value to know number of digits

for (int i = 0; i < n; i++) { int digit = (arr[i] / exp) % 10; count[digit]++; }

Count occurrences of current digit

for (int i = 1; i < 10; i++) { count[i] += count[i - 1]; }

Accumulate counts to get positions

for (int i = n - 1; i >= 0; i--) { int digit = (arr[i] / exp) % 10; output[count[digit] - 1] = arr[i]; count[digit]--; }

Place elements in output array in stable order

for (int i = 0; i < n; i++) { arr[i] = output[i]; }

Copy sorted output back to original array

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

Repeat counting sort for each digit place

Output

Original array:

170 -> 45 -> 75 -> 90 -> 802 -> 24 -> 2 -> 66 -> null

Sorted array:

2 -> 24 -> 45 -> 66 -> 75 -> 90 -> 170 -> 802 -> null

Complexity Analysis

Time: O(d * (n + k)) where d is number of digits, n is number of elements, k=10 for digits; because we do counting sort for each digit

Space: O(n + k) for output and count arrays used in counting sort

vs Alternative: Compared to comparison sorts like quicksort O(n log n), radix sort can be faster for fixed digit size numbers because it sorts in linear time relative to input size

Edge Cases

Empty array

No sorting needed, function handles gracefully

DSA C

if (n == 0) return; // Added guard in radixSort to handle empty array

Array with one element

Returns the same single element array

DSA C

for (int exp = 1; max / exp > 0; exp *= 10) { countingSort(arr, n, exp); } // loop runs once

All elements are the same

Sorting keeps array unchanged

DSA C

countingSort uses stable counting sort, so duplicates stay in order

When to Use This Pattern

When you need to sort integers or fixed-length strings efficiently without comparisons, reach for radix sort because it sorts by digits in linear time.

Common Mistakes

Mistake: Not using stable counting sort causes incorrect order for equal digits
Fix: Build output array from right to left to maintain stability

Mistake: Forgetting to process all digit places up to max number's highest digit
Fix: Use loop condition max / exp > 0 to cover all digits

Summary

Radix sort sorts numbers digit by digit from least to most significant.

Use it to sort large lists of integers efficiently when digit length is limited.

The key insight is sorting by each digit with a stable sort leads to fully sorted array.

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