Radix Sort Explained : Simple Path to Faster Sorting

Sorting is a fundamental operation in programming, essential for organizing data and optimizing search operations. While numerous algorithms exist for sorting, such as quicksort and merge-sort, one lesser-known but highly efficient method is Radix Sort. This article delves into how Radix Sort works, its advantages, and potential use cases.

What is Radix-sort?

Radix Sort is a non-comparative sorting algorithm that sorts numbers by processing individual digits. Unlike comparison-based algorithms, which evaluate the order of elements, Radix Sort groups numbers based on their digits, effectively categorizing them to achieve a sorted order.

How Radix sort Works ?

Radix Sort operates in a multi-phase process, typically involving two main steps: digit extraction and stable sorting. The process can be broken down as follows:

1. Identify the Maximum Number:

First, determine the largest number in the array. This step is crucial as it helps identify the number of digits in the largest number, guiding the sorting process.

2. Sorting by Each Digit:

The algorithm sorts the array multiple times, starting from the least significant digit (LSD) to the most significant digit (MSD). For each digit position:

• Extract the relevant digit from each number.
• Use a stable sorting algorithm (such as Counting Sort) to sort the numbers based on the current digit. Stability ensures that numbers with the same digit retain their relative order from the previous sorting phase.
• The process repeats for each digit, moving from the least significant to the most significant. By the time the most significant digit is processed, the array will be fully sorted.

Let's understand this using an Example :

Consider the example of an array [ 83 , 72 , 348 , 291 , 3 , 95 , 876 ]

Step 1: Identify the Maximum Number

First, determine the maximum number in the array to establish how many digits we need to process.

Original Array: [83, 72, 348, 291, 3, 95, 876]

Maximum Number: 876

Number of Digits: The maximum number has 3 digits.

Step 2: Loop Through Each Digit Position

Run a loop that iterates through each digit position, starting from the least significant digit (units place) and moving to the most significant digit.

Initialization: Start with position = 1 (units place). This will be multiplied by 10 in each iteration to cover tens and hundreds.

Step 3: Perform Counting Sort for Each Position

For each iteration, extract the digit at the current position and sort the array using Counting Sort.

Iteration 1: Units Position (position = 1)

1. Extract Digits: From each number, extract the last digit using (number / position) % 10.
2. For the array [83, 72, 348, 291, 3, 95, 876], the digits are:

83 → 3  
72 → 2
348 → 8
291 → 1 
3 → 3 
95 → 5
876 → 6         

3. Extracted Digits: [3, 2, 8, 1, 3, 5, 6]

4. Count Frequencies: Create a frequency array of size 10 (for digits 0-9).

5. Count the occurrences: Frequency array: [0, 1, 1, 2, 0, 1, 1, 0, 1, 0]

6. Cumulative Frequencies: Convert the frequency array to cumulative frequencies, Cumulative Array is [0, 1, 2, 4, 4, 5, 6, 6, 7, 7]

7. Build Output Array: Create an output array to hold the sorted numbers based on the current digit. Place each number in the output array using the cumulative frequencies: Output: After processing, the output array will be: [291, 72, 83, 3, 95, 876, 348].

Iteration 2: Tens Position (position = 10)

1. Extract Digits: For the array [291, 72, 83, 3, 95, 876, 348], the digits at the tens position are:

291 → 9
72 → 7
83 → 8
3 → 0
95 → 9
876 → 7
348 → 4        

Extracted Digits: [9, 7, 8, 0, 9, 7, 4]

2. Count Frequencies:

Now Frequency array: [1, 0, 0, 0, 1, 0, 0, 2, 1, 2]

3. Cumulative Frequencies: Cumulative array: [1, 1, 1, 1, 2, 2, 2, 4, 5, 7]

4. Build Output Array:

After processing, the output array will be: [3, 348, 72, 83, 876, 291, 95].

5. Copy Back to Original Array:

Array after Iteration 2: [3, 348, 72, 83, 876, 291, 95].

Iteration 3: Hundreds Position (position = 100)

1. Extract Digits:

For the array [3, 348, 72, 83, 876, 291, 95], the digits at the hundreds position are:

3 → 0
348 → 3
72 → 0
83 → 0
876 → 8
291 → 2
95 → 0         

Extracted Digits: [0, 3, 0, 0, 8, 2, 0]

2. Count Frequencies: Frequency array: [5, 0, 1, 1, 0, 0, 0, 0, 1, 0]

3. Cumulative Frequencies: Cumulative array: [5, 5, 6, 7, 7, 7, 7, 7, 8, 8]

4. Build Output Array: After processing, the output array will be: [3, 72, 83, 291, 348, 876, 95]. 5. Copy Back to Original Array: Final Sorted Array: [3, 72, 83, 291, 348, 876, 95].

import java.util.Arrays;
public class radixSort {
    public static void sort(int[] nums){
        int max=Arrays.stream(nums).max().getAsInt();
        /*
         * This loop iterates over each digit position, starting from the least
         * significant digit (i.e., i = 1 corresponds to the units place). The loop
         * continues until the maximum number in the array is fully processed. In each
         * iteration, the countSort method is called to sort the array based on the
         * current digit position.
         */
        for(int i=1;max/i>0;i*=10){
            countSort(nums,i);
        }
        System.out.println("Final sorted Array : "+Arrays.toString(nums));
    }
    
    /*
     * This method performs a counting sort on the array based on the given digit
     * position. It uses an array of frequencies to count the occurrences of each
     * digit at the given position, and then uses these frequencies to determine the
     * final position of each number in the sorted array.
     */
    private static void countSort(int[] nums,int expr){
       int n=nums.length;
       //output array to store the numbers after sorted according to each digit's base
       int[] output=new int[n];
       //create frequency array to store the frequency of each digit of the numbers of the nums array
       int[] freq=new int[10];
       //fill with zeros 
       Arrays.fill(freq,0);
       //calculate frequency and store it in the freq array
       for(int i=0;i<n;i++){
        freq[(nums[i]/expr)%10]++;
       }

       // This loop calculates the cumulative frequencies of each digit at the given
       // position. This is necessary to determine the final position of each number in
       // the sorted array.
       for(int i=1;i<10;i++){
        freq[i]=freq[i]+freq[i-1];
       }
      
       /*
        * This loop places each number in the output array based on its digit at the
        * given position. The index of the output array is determined using the
        * cumulative frequencies calculated earlier.
        */
       for(int i=n-1;i>=0;i--){
        output[freq[(nums[i]/expr)%10]-1] =nums[i];
        freq[(nums[i]/expr)%10]--;
       }
      
       //replace the original array with the output array which is sorted according to the current digit 
       System.arraycopy(output, 0, nums, 0, n);
        }
    public static void main(String[] args) {
        int []nums={83,72,348,291,3,95,876};
        sort(nums);
    }
}
        

Please visit the github link for the code : https://github.com/akashdas031/DSA/blob/main/Sorting/radixSort.java

Complexity Analysis :

Time Complexity

• Overall Time Complexity: O(d * (n + k)), where d is the number of digits in the maximum number n is the number of elements in the array .k is the range of the digit values (0-9 for base 10).

Space Complexity :

• O(n + k) due to the additional arrays used for output and frequency counting.

Advantages of Radix Sort :

• Efficiency: Particularly effective for large datasets with a fixed number of digits.
• Stability: Maintains the relative order of equal elements, which can be essential for certain applications.
• Non-comparative: Unlike traditional sorting algorithms, it does not rely on comparisons between elements.

Disadvantages of Radix Sort :

Radix Sort has several advantages, but it also comes with some disadvantages. Here are the key drawbacks:

• Space Complexity: Radix Sort requires additional space for the counting array and output array, which can be significant, especially for large datasets. This can be a concern in memory-constrained environments.
• Limited to Certain Data Types:Radix Sort is primarily effective for sorting integers or strings. It is not suitable for general comparison-based sorting of arbitrary objects without a defined way to extract keys.
• Performance with Large Key Ranges: If the range of the input values is large compared to the number of items, the counting array can become very large, leading to inefficiency in terms of both space and time.

Conclusion :

In this article, we explored Radix Sort, a unique sorting algorithm that operates based on the individual digits of the numbers being sorted. By providing a clear example, we demonstrated how Radix Sort efficiently organizes data, particularly in cases where the elements have fixed lengths. We also discussed the algorithm's time complexity, which can achieve linear performance under certain conditions, and its space complexity, which requires additional memory for sorting.

While Radix Sort has several advantages, including its efficiency with large datasets and stability, it also has limitations, such as higher space requirements and the necessity of fixed-length keys. Understanding these factors allows you to determine when Radix Sort is the right choice for your sorting needs.

We hope this article has equipped you with valuable insights into Radix Sort, its workings, and its applicability.

We would love to hear your feedback! Did you find the information helpful? Are there any aspects you would like to learn more about? Your thoughts and questions are important to us, so please share them in the comments below!

Happy Coding !!!