Radix Sort Algorithm

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:

Radix Sort Algorithm

 

 

MCQs on Radix Sort

 

 

Recommended Articles for you: