Radix Sort – Explanation, Pseudocode and Implementation

Radix Sort is a non-comparative sorting algorithm with asymptotic complexity O(nd). It is one of the most efficient and fastest linear sorting algorithms. Radix sort was developed to sort large integers. As an integer is treated as a string of digits so we can also call it a string sorting algorithm.

1. Radix Sort Complexity Analysis

The lower bound for the comparison-based sorting algorithm is O(n*log n) like merge sort, quick sort, heap sort.

So radix sort is efficient than the comparison sorting algorithm until the number of digits (key) is less than log n.

Counting sort can’t be used if a range of key-value is large (suppose range is 1 to n²) so radix sort is the best choice to sort in linear time.

We use counting sort to sort elements of every digit, so time complexity is O(nd).

2. How Radix Sort works

• In radix sort, we first sort the elements based on the last digit (least significant digit).
• Then the result is again sorted by the second digit, continue this process for all digits until we reach the most significant digit.

3. Key points for radix sort algorithm

• Radix Sort is a linear sorting algorithm.
• The time complexity of Radix Sort is O(nd), where n is the size of the array and d is the number of digits in the largest number.
• It is not an in-place sorting algorithm as it requires extra additional space.
• Radix Sort is a stable sort as the relative order of elements with equal values is maintained.
• 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.

4. Radix Sort Example with Explanation

Observe the image given below carefully and try to visualize the concept of this algorithm.

Let’s discuss the above example in detail:

For 1^st pass: we sort the array on basis of the least significant digit (1s place) using counting sort. Notice that 435 is below 835 because 435 occurred below 835 in the original list.

For 2^nd pass: we sort the array on basis of the next digit (10s place) using counting sort. Notice that here 608 is below 704, because 608 occurred below 704 in the previous list, and similarly for (835, 435) and (751, 453).

For 3^rd pass: we sort the array on basis of the most significant digit (100s place) using counting sort. Notice that here 435 is below 453, because 435 occurred below 453 in the previous list, and similarly for (608, 690) and (704, 751).

5. Pseudocode of Radix Sort

Let’s implement the pseudocode for the Radix sort and understand how it works.

Radix-Sort(A, d)
//It works same as counting sort for d number of passes.
//Each key in A[1..n] is a d-digit integer.
//(Digits are numbered 1 to d from right to left.)
    for j = 1 to d do
        //A[]-- Initial Array to Sort
        int count[10] = {0};
        //Store the count of "keys" in count[]
        //key- it is number at digit place j
        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]

        //Build the resulting array by checking
        //new position of A[i] from count[k]
        for i = n-1 downto 0 do
         result[ count[key of(A[i])] ] = A[j]
         count[key of(A[i])]--

        //Now main array A[] contains sorted numbers
        //according to current digit place
        for i=0 to n do
          A[i] = result[i]

    end for(j)
end func

6. Asymptotic Analysis of Radix Sort

In the Radix sort algorithm running time depends on the intermediate sorting algorithm which is counting sort.

If the range of digits is from 1 to k, then counting sort time complexity is O(n+k).

There are d passes i.e counting sort is called d time, so total time complexity is O(nd+nk) =O(nd). As k=O(n) and d is constant, so radix sort runs in linear time.

Worst Case Time complexity: O (nd)
Average Case Time complexity: O(nd)
Best Case Time complexity: O(nd)
Space Complexity: O(n+k)
Data Structure: Array
Sorting In Place: No
Stable: Yes

7. Implementation of Radix Sort in C Language

Let’s implement Radix sort in C Programming language.

// C implementation of Radix Sort
#include<stdio.h>
#include<stdlib.h>

// This  function gives maximum value in array[]
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;
}

// Main Radix Sort sort function
void radixSort(int A[], int n)
{
    int i,digitPlace = 1;
    int result[n]; // resulting array
    // Find the largest number to know number of digits
    int largestNum = getMax(A, n);


    //we run loop until we reach the largest digit place
    while(largestNum/digitPlace >0){

        int count[10] = {0};
         //Store the count of "keys" or digits in count[]
        for (i = 0; i < n; i++)
            count[ (A[i]/digitPlace)%10 ]++;

        // Change count[i] so that count[i] now contains actual
        //  position of this digit in result[]
        //  Working similar to the counting sort algorithm
        for (i = 1; i < 10; i++)
            count[i] += count[i - 1];

        // Build the resulting array
        for (i = n - 1; i >= 0; i--)
        {
            result[count[ (A[i]/digitPlace)%10 ] - 1] = A[i];
            count[ (A[i]/digitPlace)%10 ]--;
        }

        // Now main array A[] contains sorted
        // numbers according to current digit place
        for (i = 0; i < n; i++)
            A[i] = result[i];

            // Move to next digit place
            digitPlace *= 10;
    }
}

// Function to print an array
void printArray(int A[], int n)
{
    int i;
    for (i = 0; i < n; i++)
    printf("%d ", A[i]);
    printf("\n");
}

// Driver program to test above functions
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;
}

Output:-
Unsorted array:  209,3,48,91,66,101,30,795
Sorted array:    3,30,48,66,91,101,209,795

8. Radix Sort Implementation in Java

Let’s implement Radix sort in Java Programming language.

/* Java implementation Radix Sort */
package codingeek;
import java.util.Arrays;
import java.util.Scanner;

public class RadixSort {
	
	public static void main(String arg[]){
		
		int a[] = {209,3,48,91,66,101,30,795};
		//print unsorted array using Arrays.toString()
	    System.out.print("Unsorted array: ");
        System.out.println(Arrays.toString(a)); 
		
		RadixSort rs= new RadixSort();
	    rs.radixSort(a);
	
	    System.out.print("Sorted array: ");
        //print sorted array
        System.out.println(Arrays.toString(a)); 
	    
	}
	
	// This  function gives maximum value in array[]
	public int getMax(int A[])
	{
	    int max = A[0];
	    for (int i = 1; i < A.length; i++){
	        if (A[i] > max)
	            max = A[i];
	    }
	    return max;
	}
	
	// Main Radix Sort sort function
	public void radixSort(int A[])
	{
	    int digitPlace = 1;
	    int n=A.length;
	    int result[]=new int[n]; // resulting array
	    // Find the largest number to know number of digits
	    int largestNum = getMax(A);
	
	
	    //we run loop until we reach the largest digit place
	    while(largestNum/digitPlace >0){
	    	
	        int count[]=new int[10];
	        //Initializing counting array C[] to 0
		    for (int i=0; i <10; i++)
		        count[i] = 0;
		        
	         //Store the count of "keys" or digits in count[]
	        for (int i = 0; i < n; i++)
	            count[ (A[i]/digitPlace)%10 ]++;
	
	        // Change count[i] so that count[i] now contains actual
	        //  position of this digit in result[]
	        //  Working similar to the counting sort algorithm
	        for (int i = 1; i < 10; i++)
	            count[i] += count[i - 1];
	
	        // Build the resulting array
	        for (int i = n - 1; i >= 0; i--)
	        {
	            result[count[ (A[i]/digitPlace)%10 ] - 1] = A[i];
	            count[ (A[i]/digitPlace)%10 ]--;
	        }
	
	        // Now main array A[] contains sorted
	        // numbers according to current digit place
	        for (int i = 0; i < n; i++)
	            A[i] = result[i];
	
	            // Move to next digit place
	            digitPlace *= 10;
	    }
	}

}

Output:-
Unsorted array:  209,3,48,91,66,101,30,795
Sorted array:    3,30,48,66,91,101,209,795

9. Conclusion

• Radix Sort is one of the most efficient and fastest linear sorting algorithms. It is simple to understand and easy to implement.
• Radix Sort is a good choice for many programs that need a fast sort.
• Radix Sort can handle larger keys more efficiently as compare to Counting Sort.
• Radix sort is almost equally efficient as the best comparison-based sorts (and worse if keys are much longer than log n).
• Another linear sorting algorithm is bucket sort which we will discuss in the future post.

Helpful Links

Data Structure tutorials
Algorithm Tutorials

All examples are hosted on Github.

An investment in knowledge always pays the best interest. I hope you like the tutorial. Do come back for more because learning paves way for a better understanding

Do not forget to share and Subscribe.

Happy coding!! ?

Recommended -