C Exercises: Radix sort algorithm

C Programming Searching and Sorting Algorithm: Exercise-7 with Solution

Write a C program to sort a list of elements using the Radix sort algorithm.

Note: Radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value.

Sample Solution:

Sample C Code:

#include <stdio.h>
// Function to print the elements of an array
int print(int *a, int n) {
    int i;
    for (i = 0; i < n; i++)
        printf("%d\t", a[i]);
}
// Function to perform radix sort on array a with n elements
void radix_sort(int *a, int n) {
    int i, b[10], m = 0, exp = 1;
    // Find the maximum element in the array
    for (i = 0; i < n; i++) {
        if (a[i] > m)
            m = a[i];
    }

    // Iterate through each digit place (units, tens, hundreds, etc.)
    while (m / exp > 0) {
        // Initialize an array to count occurrences of each digit (0 to 9)
        int box[10] = {0};
        // Count occurrences of each digit at the current place
        for (i = 0; i < n; i++)
            box[a[i] / exp % 10]++;
        // Update the count array to contain the cumulative count of digits
        for (i = 1; i < 10; i++)
            box[i] += box[i - 1];
        // Build the output array by placing elements in their correct order
        for (i = n - 1; i >= 0; i--)
            b[--box[a[i] / exp % 10]] = a[i];
        // Copy the sorted elements back to the original array
        for (i = 0; i < n; i++)
            a[i] = b[i];
        // Move to the next digit place
        exp *= 10;
    }
}
int main() {
    int arr[10];
    int i, num;
    // Input the number of elements
    printf("Input number of elements: ");
    scanf("%d", &num);
    // Input array elements one by one
    printf("\nInput array elements one by one: ");
    for (i = 0; i < num; i++)
        scanf("%d", &arr[i]);
    // Display the original array elements
    printf("\nArray elements: ");
    print(&arr[0], num);
    // Perform radix sort on the array
    radix_sort(&arr[0], num);
    // Display the sorted array elements
    printf("\nSorted elements: ");
    print(&arr[0], num);

    return 0;
}

Sample Input:

3
12
15
56

Output:

Input  number of elements: 
Input  array elements one by one : 
Array  elements : 12	15	56	
Sorted  elements : 12	15	56

Flowchart:

C Programming Code Editor:

Previous: Write a C program to sort a list of elements using the quick sort algorithm.
Next: Write a C Program for counting sort.