Radix Sort

Reading time: 25 minutes | Coding time: 10 minutes

Radix Sort is an efficient non-comparison based sorting algorithm which can sort a dataset in linear O(N) time complexity and hence, can be better than other competitive algorithm like Quick Sort. It uses another algorithm namely Counting Sort as a subroutine.

Radix Sort takes advantage of the following ideas:

  • Number of digits in an Integer is determined by:
    • its base
    • very less compared to the data

Numbers increase linearly but number of digits increase logarithmically.

Radix sort was developed to sort large integers. It considers integer as a string of digits so we can use Radix Sort to sort strings as well.

Algorithm

  • Do following for each digit i where i varies from least significant digit to the most significant digit.
    • Sort input array using counting sort (or any stable sort) according to the i’th digit.

Example


Assume the input array is:

[326, 453, 608, 835, 751, 435, 704, 690]

Based on the algorithm, we will sort the input array according to the one's digit (least significant digit).

The original array is sorted based on [6, 3, 8, 5, 1, 5, 4, 0] using Counting Sort

So, the array becomes [690, 751, 453, 704, 835, 435, 326, 608]

Now, we'll sort according to the ten's digit:

The above partially sorted array is sorted based on [9, 5, 5, 0, 3, 3, 2, 0] using Counting Sort

Now, the array becomes : [704, 608, 326, 835, 435, 751, 453, 690]

Finally , we sort according to the hundred's digit (most significant digit):

The above partially sorted array is sorted based on [7, 6, 3, 8, 4, 7, 4, 6] using Counting Sort

The array becomes : [326, 435, 453, 608, 690, 704, 751, 835] which is sorted.

Follow this image to understand the concept:

image of radix sort

Why does sorting one digit place at a time work in Radix Sort?

Maintains the order of input data
It is in-place sorting
Uses counting sort
It is non comparison based
As Radix Sort maintains the order of the input data, the sorting of previous digits are maintained and adjusted only if the higher significant digit needs to be sorted.

Pseudocode


Radix-Sort(A, d)
       for j = 1 to d do
            int count[10] = {0};
            for i = 0 to n do
                count[key of(A[i]) in pass j]++
            for k = 1 to 10 do
                count[k] = count[k] + count[k-1]
            for i = n-1 downto 0 do
                result[ count[key of(A[i])] ] = A[j]
                count[key of(A[i])]--
            for i=0 to n do
                A[i] = result[i]
       end for(j)
 end func 
 

Complexity Analysis


Best case time complexity:Ω(nk)

Average case time complexity:Θ(nk)

Worst case time complexity:O(nk)

Space complexity:O(n+k)

where n is the number of input data and k is the maximum element in the input data

Let there be d digits in input integers. Radix Sort takes O(d(n+b))* time where b is the base for representing numbers, for example, for decimal system, b is 10. What is the value of d? If k is the maximum possible value, then d would be O(logb(k)). So overall time complexity is O((n+b) * logb(k)). Which looks more than the time complexity of comparison based sorting algorithms for a large k.

Let us first limit k. Let k <= nc where c is a constant. In that case, the complexity becomes O(nLogb(n)). But it still doesn’t beat comparison based sorting algorithms.

What if we make value of b larger?. What should be the value of b to make the time complexity linear? If we set b as n, we get the time complexity as O(n). In other words, we can sort an array of integers with range from 1 to nc if the numbers are represented in base n (or every digit takes log2(n) bits).

Implementation


  • C
  • Java

C


#include<stdio.h>
#include<stdlib.h>
int getMax(int A[], int n)
{   int i;
    int max = A[0];
    for (i = 1; i < n; i++){
        if (A[i] > max)
            max = A[i];
 }
    return max;
    }
void radixSort(int A[], int n)
{   int i,digitPlace = 1;
    int result[n];
    int largestNum = getMax(A, n);
    while(largestNum/digitPlace >0){
        int count[10] = {0};
        for (i = 0; i < n; i++)
            count[ (A[i]/digitPlace)%10 ]++;
        for (i = 1; i < 10; i++)
            count[i] += count[i - 1];
        for (i = n - 1; i >= 0; i--)
        {   result[count[ (A[i]/digitPlace)%10 ] - 1] = A[i];
            count[ (A[i]/digitPlace)%10 ]--;
        }
        for (i = 0; i < n; i++)
            A[i] = result[i];
            digitPlace *= 10;
    }
}
void printArray(int A[], int n)
{   int i;
    for (i = 0; i < n; i++)
    printf("%d ", A[i]);
    printf("\n");
}
int main()
{   int a[] = {209,3,48,91,66,101,30,795};
    int n = sizeof(a)/sizeof(a[0]);
    printf("Unsorted Array: ");
    printArray(a, n);
    radixSort(a, n);
    printf("Sorted Array: ");
    printArray(a, n);
    return 0;
}

Java


import java.io.*; 
import java.util.*; 
class Radix { 
           static int getMax(int arr[], int n){ 
           int mx = arr[0]; 
           for (int i = 1; i < n; i++) 
                 if (arr[i] > mx) 
                        mx = arr[i]; 
           return mx; 
    } 
   static void countSort(int arr[], int n, int exp) 
    {   
           int output[] = new int[n]; 
           int i; 
           int count[] = new int[10]; 
           Arrays.fill(count,0);
           for (i = 0; i < n; i++) 
                   count[ (arr[i]/exp)%10 ]++; 
           // Change count[i] so that count[i] now contains 
           // actual position of this digit in output[] 
           for (i = 1; i < 10; i++) 
                   count[i] += count[i - 1]; 
           // Build the output array 
           for (i = n - 1; i >= 0; i--){
                   output[count[ (arr[i]/exp)%10 ] - 1] = arr[i]; 
                   count[ (arr[i]/exp)%10 ]--; 
        }
           for (i = 0; i < n; i++) 
                   arr[i] = output[i]; 
    } 
   static void radixsort(int arr[], int n) 
       { // Find the maximum number to know number of digits 
           int m = getMax(arr, n);
           for (int exp = 1; m/exp > 0; exp *= 10) 
                  countSort(arr, n, exp); 
    } 
   static void print(int arr[], int n) 
    { 
        for (int i=0; i<n; i++) 
               System.out.print(arr[i]+" "); 
    } 
    public static void main (String[] args) 
    {    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66}; 
         int n = arr.length; 
         radixsort(arr, n); 
         print(arr, n); 
    } 
} 

Advantages

The advantages of Radix Sort are:

  • Fast when the keys are short i.e. when the range of the array elements is less.
  • Used in suffix array constuction algorithms like Manber's algorithm and DC3 algorithm.
  • Radix Sort is stable sort as relative order of elements with equal values is maintained.

Disadvantages

The disadvantages of Radix Sort are:

  • Since Radix Sort depends on digits or letters, Radix Sort is much less flexible than other sorts. Hence , for every different type of data it needs to be rewritten.
  • The constant for Radix sort is greater compared to other sorting algorithms.
  • It takes more space compared to Quicksort which is inplace sorting.
  • Radix sort can be slower than other sorting algorithms like merge sort and quick sort, if the operations are not efficient enough. These operations include inset and delete functions of the sub-list and the process of isolating the digits we want.
  • Radix sort is less flexible than other sorts as it depends on the digits or letter. Radix sort needs to be rewritten if the type of data is changed.
  • It is not an in-place sorting algorithm as it requires extra additional space.