This blog post explains the Radix Sort Algorithm and its implementation using the C programming language. So before writing the C code for the Radix Sort let’s first understand the Radix Sort.

What is Radix Sort Algorithm:

Radix sort is a non-comparative sorting algorithm. It avoids comparison by creating and distributing elements into buckets according to their radix.

Radix sort similar to Counting sort and Bucket sort. Counting Sort is also not a comparison-based algorithm. It has the O(n+k) complexity, where k is the maximum element of the input array. So, if k is O(n), CountSort becomes linear sorting.

The Radix Sort algorithm is an extended version of the counting sort to get a better time complexity when k goes O(n2).

Radix Sort example code:

Now let’s see the example code for the Radix Sort using the C programming language.

// Radix Sort in C Programming
#include <stdio.h>
#include<string.h>


// Using counting sort to sort the elements in the basis of significant places
void countingSort(int array[], int size, int place)
{
    int i = 0;
    int output[size + 1]; //output array
    int max = (array[0] / place) % 10;

    for (i = 1; i < size; i++)
    {
        if (((array[i] / place) % 10) > max)
        {
            max = array[i];
        }
    }

    // Create a count array to store count of individual
    // characters and initialize count array as 0
    int count[max + 1];
    memset(count, 0, sizeof(count));


    // Calculate count of elements
    for (i = 0; i < size; i++)
    {
        count[(array[i] / place) % 10]++;
    }

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

    // Place the elements in sorted order
    for (i = size - 1; i >= 0; i--)
    {
        output[count[(array[i] / place) % 10] - 1] = array[i];
        count[(array[i] / place) % 10]--;
    }

    for (i = 0; i < size; i++)
    {
        array[i] = output[i];
    }
}

// Main function to implement radix sort
void radixsort(int array[], int size)
{
    int i,place;
    // Find the largest element of the array
    int max = array[0];
    for (i = 1; i < size; i++)
    {
        if (array[i] > max)
        {
            max = array[i];
        }
    }

    // Do counting sort for every digit. Note that instead
    // of passing digit number, place is passed. place is 10^i
    // where i is current digit number
    for (place = 1; max / place > 0; place *= 10)
    {
        countingSort(array, size, place);
    }
}

//print array element
void printArray(int arr[], int array_size)
{
    int i;
    for (i = 0; i < array_size; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}


int main()
{
    //input array
    int arr[] = {18,4, 0, 2, 8, 9, 3, 1};

    //calculate array size
    int array_size = sizeof(arr) / sizeof(arr[0]);

    radixsort(arr, array_size);

    printArray(arr, array_size);

    return 0;
}

Output:

MCQs on Radix Sort

Recommended Articles for you:

• Counting Sort Algorithm with example programming code.
• Bubble Sort Algorithm with example programming code.
• Quickselect Algorithm with example code.
• Best keyboards for the programmers.
• Merge Sort algorithm with example code.
• Quick Sort Algorithm with example code.
• Best programming laptop for programmers.
• How do you reverse an array in C?
• C program to find the Median of two sorted arrays of different sizes.
• Basics of the recursive function.
•  C program to rearrange array such that even positioned are greater than odd.
• How to rotate an array left and right by a given number K?
• Why is it faster to process sorted array than an unsorted array?
• How to access 2d array in C?
• How to remove duplicates from a given array in C?
• Array interview questions.
• How to create dynamic array in C?
• How to pass an array as a parameter in C?