C Program for Radix Sort with Example and Explanation

A C program for radix sort uses counting sort on each digit from least significant to most significant; the main code loops over digit places and sorts the array accordingly.

Examples

Input170 45 75 90 802 24 2 66

OutputSorted array: 2 24 45 66 75 90 170 802

Input5 3 8 6 2

OutputSorted array: 2 3 5 6 8

Input1

OutputSorted array: 1

How to Think About It

To sort numbers using radix sort, think of sorting them digit by digit starting from the rightmost digit. For each digit place, use a stable sorting method like counting sort to reorder the numbers based on that digit. Repeat this for all digit places until the whole array is sorted.

Algorithm

1

Find the maximum number in the array to know the number of digits.

2

For each digit place (ones, tens, hundreds, etc.):

3

Use counting sort to sort the array based on the current digit.

4

Repeat until all digit places are processed.

5

Return the sorted array.

Code

c

#include <stdio.h>

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;
}

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 m = getMax(arr, n);
    for (int exp = 1; m / 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);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

Output

Sorted array: 2 24 45 66 75 90 170 802 

Dry Run

Let's trace the array [170, 45, 75, 90, 802, 24, 2, 66] through the radix sort code.

1

Find maximum

Maximum number is 802.

2

Sort by 1's digit

Sort array by last digit: [170, 90, 802, 2, 24, 45, 75, 66]

3

Sort by 10's digit

Sort array by tens digit: [802, 2, 24, 45, 66, 170, 75, 90]

4

Sort by 100's digit

Sort array by hundreds digit: [2, 24, 45, 66, 75, 90, 170, 802]

Step	Array State
Initial	170 45 75 90 802 24 2 66
After sorting by 1's digit	170 90 802 2 24 45 75 66
After sorting by 10's digit	802 2 24 45 66 170 75 90
After sorting by 100's digit	2 24 45 66 75 90 170 802

Why This Works

Step 1: Find maximum number

We find the largest number to know how many digits we need to sort by.

Step 2: Counting sort by digit

For each digit place, counting sort rearranges numbers based on that digit, preserving order of previous digits.

Step 3: Repeat for all digits

Sorting from least significant to most significant digit ensures the whole array becomes sorted.

Alternative Approaches

LSD Radix Sort with Linked Lists

c

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

// This version uses linked lists for buckets instead of arrays
// Code omitted for brevity but uses bucket lists for each digit
int main() {
    // Implementation would be longer and more complex
    return 0;
}

Using linked lists for buckets can handle dynamic sizes but is more complex and slower than array counting.

MSD Radix Sort

c

#include <stdio.h>
// MSD sorts from most significant digit first, requires recursion
// Code omitted for brevity
int main() {
    return 0;
}

MSD radix sort can be faster for some data but is more complex and uses recursion.

Complexity: O(d * (n + k)) time, O(n + k) space

Time Complexity

Radix sort runs in O(d * (n + k)) where d is number of digits, n is number of elements, and k is digit range (usually 10). Each digit requires counting sort which is O(n + k).

Space Complexity

Extra space is needed for output array and count array, so O(n + k). The sort is not in-place.

Which Approach is Fastest?

Radix sort is faster than comparison sorts for large n with small digit range. MSD radix can be faster for some data but is more complex.

Approach	Time	Space	Best For
LSD Radix Sort (Counting Sort)	O(d*(n+k))	O(n+k)	General integer sorting with fixed digit size
MSD Radix Sort	O(d*(n+k))	O(n+k)	Sorting with variable length keys, prefix sorting
Comparison Sorts (e.g., QuickSort)	O(n log n)	O(log n)	General purpose sorting, unknown digit size