Radix Sort

How Does Radix Sort Algorithm Work?

Radix Sort works by sorting numbers digit by digit. It starts from the LSD to MSD. These are the steps of working of radix sort algorithm:

1. Determine the Maximum Digit Length:

• Identify the maximum number of digits in the largest number in the array. This determines how many passes or iterations Radix Sort will require.

2. Sort by Each Digit:

• Begin with the least significant digit (the rightmost digit) and perform a stable sort based on this digit.
• Move to the next significant digit and repeat the sorting process.
• Continue this process for each digit position from right to left until the most significant digit (the leftmost digit) is sorted.

3. Use Counting Sort for Stability:

• Radix Sort typically uses Counting Sort or another stable sorting algorithm as the subroutine for sorting digits. Counting Sort is efficient for this purpose as it ensures that the relative order of elements with the same digit is preserved.

4. Distribute Numbers into Buckets:

• For each digit position, distribute the numbers into buckets based on the value of the current digit. For example, if sorting by the unit place, numbers are distributed into 10 buckets (0-9).

5. Reassemble the Array:

• Collect the numbers from the buckets in order and reassemble them into a single array. This step ensures that the numbers are sorted according to the current digit.

6. Repeat for All Digit Positions:

• Repeat the sorting and bucket distribution process for each digit position until all digits have been processed.

Radix sort from counting sort

Radix sort is of two types-LSD (least significant digit), where it starts from the end of the string (least significant value), or MSD (most significant digit), where the sorting starts from the beginning of the string(most significant value).

In the given example, we will be using LSD-the elements will first be sorted based on their unit place using counting sort, then their tens place and so on till the most significant place.

Example of Radix Sort

Let’s consider an array of elements 112, 473, 514, 59, 1, 45, 788 and use counting sort to sort the elements beginning from the units place:

Algorithm

• The maximum element of the initial array is stored in variable ‘K’.
• ‘Count’ array is created with all elements initially being 0, and then the count is incremented every time the number at the index occurs in the array.
• Next, we calculate the cumulative count and the elements are placed in sorted order after counting sort.
• A function is made to retrieve the largest element in the array and then finally a function is made to implement radix sort after counting sort.
• In this function, the maximum element is stored and elements are sorted bases on place value.
• The function is then called and the sorted array is printed.

Code snippet for the given example:

• Java

Java

class radixSort

{



  // Counting sort to sort the elements based on the number of digits

  void countingSort(int array[], int digits, int place)

  {

    int[] output = new int[digits + 1];

    int max = array[0];

    for (int i = 1; i < digits; i++)

    {

      if (array[i] > max)

        max = array[i];

    }

    int[] count = new int[max + 1];

    for (int i = 0; i < max; ++i)

      count[i] = 0;



    // Calculating the count for elements

    for (int i = 0; i < digits; i++)

      count[(array[i] / place) % 10]++;



    // Calculate cumulative count

    for (int i = 1; i < 10; i++)

      count[i] += count[i - 1];



    // Place the elements in sorted order

    for (int i = digits - 1; i >= 0; i--)

    {

      output[count[(array[i] / place) % 10] - 1] = array[i];

      count[(array[i] / place) % 10]--;

    }



    for (int i = 0; i < size; i++)

      array[i] = output[i];

  }



  // Function to get the largest element from an array

  int getMax(int array[], int n)

  {

    int max = array[0];

    for (int i = 1; i < n; i++)

    {

      if (array[i] > max)

       {

        max = array[i];

       }

    }

    return max;

  }



  // Main function to implement radix sort

  void radixSort(int array[], int size)

  {



    // Get maximum element

    int max = getMax(array, size);



    // Apply counting sort to sort elements based on place value.

    for (int place = 1; max / place > 0; place *= 10)

      countingSort(array, size, place);

  }



  // calling function

  public static void main(String args[])

  {

    int[] data = { 112, 473, 514, 59, 1, 45, 788 };

    int size = data.length;

    RadixSort rs = new RadixSort();

    rs.radixSort(data, size);

    System.out.println("Sorted array in ascending Order: ");

    System.out.println(Arrays.toString(data));

  }

}

You can also try this code with Online Java Compiler

Run Code

Output

Time Complexity

The time complexity of radix sort isT(N) = O(D * (N + B) ), ‘D’ being the number of digits in a number, ‘N’ being the number of elements, and ‘B’ being the base or bucket size. Usually, base 10 is used for decimal representation.

Radix sort is mostly faster than O(N * (log N)) and hence better.

Space Complexity

The space complexity for Radix sort is  N + K, ‘K’ denoting the number of digits in the maximum element in the array.

Radix sort uses Counting sort for each digit of numbers in the array. Counting sort has space complexity of O(N + K), as Counting Sort using an auxiliary space to sort every 10th place digit

Frequently Asked Questions

Can insertion sort be used as an intermediate sort for Radix sort?

Radix Sort can use any of the following to sort individual digits: Bubble sort, counting sort, insertion sort or bucket sort. This is because the runtime is O(N * K), ‘K’ being the maximum number and ‘N’ being the length of the array.

Is Quick sort better than Radix Sort?

Quick sort has an average complexity of N * log(N) and usually the lowest ‘K’ among all techniques. Radix sort however has a large value for ‘K’ and therefore quick sort is generally better and faster than Radix sort.

Can Radix Sort be used on strings?

Radix sort treats integers as strings of digits. So, despite being developed for large integers, it is actually a string sorting technique. Radix sort can either be LSD (least significant digit) or MSD (most significant digit).

What is the disadvantage of Radix sort?

The Radix Sort algorithm is dependent on letters or digits, therefore making it less flexible than other techniques. Moreover, the constraint for this technique is larger in comparison to the other techniques, and thus Radix sort takes up more space than in-place sorting techniques like Quicksort.

Conclusion

In this article, we learned about radix sort. This offers a unique approach to sorting by focusing on individual digits rather than comparing entire numbers. This non-comparative sorting algorithm shines in scenarios where you have fixed-length keys or numbers with a predictable digit range. Its efficiency stems from its ability to process digits in a stable manner, leveraging Counting Sort to handle each digit position independently.

You can go to Coding Ninjas Studio and try solving problems. Share this blog with your friends if you found it helpful!

Recommended Problems - 

• Sort 0 1 2 
• Wiggle sort
• Find first and last position in sorted array

Until then, All the best for your future endeavours, and Keep Coding.