Radix Sort

Reading time: 25 minutes | Coding time: 10 minutes

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:

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

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

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.