Radix Sort

Reet Maggo
Last Updated: May 13, 2022

Introduction

Understanding Radix Sort will require a good understanding of counting sort, which you can study here, and then this article will proceed to explain the working; and with an example, the algorithm and code for Radix Sort. Further, there will be a discussion about time complexity followed by some questions related to the topic.

What is Radix sort used for? 

Radix sort is known as an integer sorting algorithm that sorts elements by individually grouping digits based on their face value. Being a non-comparative sorting algorithm, it distributes its elements to avoid comparison.

Radix sort comes in handy when the range of elements is N ^ 2, and the implementation of counting sort cannot be implemented because it is only efficient for elements in the range 1 to ‘K’, where ‘K’ is the maximum element.

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:

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 = { 11247351459145788 };

    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));

  }

}

 

 

Output

1 45 59 112 473 514 788

 

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

 

  1. 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.


2. 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.

 

3. 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).

 

4. 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.

 

Key takeaways

In this article, we learned how the radix sort algorithm works and how it is implemented, along with an example.

 

The Radix sort algorithm is very efficient for cases where input values are lesser than or equal to the number of values to be sorted. You can go to CodeStudio and try solving problems. Share this blog with your friends if you found it helpful!

 

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

Was this article helpful ?
0 upvotes