Radix Sort

In this tutorial we will be learning about Radix sort algorithm.

About Radix Sort

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