Radix Sort

Sorting Algorithm

Share

In this tutorial we will be learning about Radix sort algorithm. In this sorting algorithm we sort the unsorted elements digit wise starting from the least significant digit to the most significant digit.

For example: If we are dealing with unsorted numbers then we know that there are 10 digits from 0 to 9 that are used to form any number. So, we will need 10 buckets labeled 0 to 9 to sort the unsorted numbers.

Sort the numbers

10, 15, 1, 60, 5, 100, 25, 50

We have some unsorted numbers
and our task is to sort them in ascending order. We know that there are 10 digits from 0 to 9. So, we will need 10 buckets labeled 0 to 9 in order to sort the given unsorted numbers.

C Code


#include <stdio.h>

//const
#define MAX 10

//function declaration
void display(int arr[], int size);
int getMax(int arr[], int size);
void radixSort(int arr[], int size);

int main() {
    //unsorted elements
    int arr[] = {10,15,1,60,5,100,25,50};

    //size of the array
    int n = sizeof(arr)/sizeof(arr[0]);

    //output unsorted elements
    display(arr, n);

    //sort the elements
    radixSort(arr, n);

    //display sorted elements
    display(arr, n);

    return 0;
}

void display(int arr[], int size) {
    int i;
    for(i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int getMax(int arr[], int size) {
    int i, max = arr[0];
    for(i = 1; i < size; i++) {
        if(arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

void radixSort(int arr[], int size) {
    int i, max, bucket[MAX], count[10], expo = 1;

    //get the max value element in the unsorted array
    max = getMax(arr, size);

    while(max / expo > 0) {
        //reset count
        for(i = 0; i < 10; i++) {
            count[i] = 0;
        }

        //save count of the occurrence
        for(i = 0; i < size; i++) {
            count[ (arr[i] / expo) % 10 ]++;
        }

        //set count to contain the actual position of the digits
        for(i = 1; i < size; i++) {
            count[i] += count [i - 1];
        }

        //build the bucket
        for(i = size - 1; i >= 0; i--) {
            bucket[ count[ (arr[i]/expo) % 10 ]  - 1] = arr[i];
            count[ (arr[i]/expo) % 10 ]--;
        }

        //copy the result to arr
        for(i = 0; i < size; i++) {
            arr[i] = bucket[i];
        }

        //increase expo, 10^x
        expo *= 10;
    }
}
Share