Radix Sort

2.6K

Radix Sort is also an unconventional sorting technique. Read more about some of the conventional sorting techniques:

• Insertion Sort
• Merge Sort
• Quick Sort

Among the other unconventional techniques like the Counting Sort and Bucket Sort this algorithm also assumes some kind of before-hand knowledge about the input elements to give you an improved time complexity. Counting Sort assumes that the input data is within a small defined range, whereas Bucket Sort assumes that the input data set is uniformly distributed. What is special about Radix Sort?

Basic Idea:

Radix sort assumes that all the input elements are from base d. It means all numbers are d-digit numbers. It may sound very weird at first, how would that even matter if you are sorting random digit numbers. However, there could be some special use cases.

What we basically do is, we first sort the elements based on the value in the unit’s place [least significant digit]. Then, we sort values based on the value of the tenth place [next to least significant digit]. Continue this process until we reach the most significant digits.

1. Take the least significant digit of each element.
2. Sort the list of elements based on that digit, but keep the order of elements with the same digit(this is the definition of stable sort).
3. Repeat the sort with each more significant digit.

How does it work?

Let us try to sort an example array using this algorithm. Suppose we have this sample array:

arr[ ] = { 121, 432, 564, 23, 1, 45, 788 }

Just a couple of seconds ago I said that, for Radix sort all the elements should be of d digits. But in this array you can see that some elements have 3 digits, some have 2 and some have 1 digit. Are we stuck now?

You can kind of convert all elements to same number of digits. 23 can be assumed as 023, and 1 as 001. This will not change the value of elements, but help to perform our steps. Once, we convert all these elements to the same number of digits, our array becomes something like this.

Now, all we need to do is sort all of these numbers “in-place” first using the digit in unit’s place, then ten’s place and ultimately hundred’s place.

Don’t worry about how the array looks in the intermediate steps. You will get the final sorted array once you have sorted the numbers using the most significant digit.

Time Complexity:

The speed of this sorting technique depends on the inner basic operations. If they are not efficient enough, Radix Sort can be slower than other techniques. These operations include insertion and deletion of elements from lists or array at respective places, and isolating the digit we want to sort upon.

Additionally, if the numbers are not of the same length we need an additional step to perform a left padding of the smaller numbers by 0. This can be the slowest part of this algorithm and the hardest to make efficient.

For radix sort, that uses counting sort as an intermediate stable sort, the time complexity is O(d * ( n + k )). Here d is the number of digits or the number cycle and O(n + k) is the time complexity for counting sort.

There is one huge drawback for this technique though. You cannot have a one size fits all implementation. We need to rewrite the logic for different data types. This makes this technique inefficient and is not commonly found.

Implementation:

  private void countingSort(int[] arr, int place) {
    int size = arr.length;
    int max = Arrays.stream(arr).max().getAsInt();
    int[] output = new int[size + 1];
    int[] count = new int[max + 1];

    // Calculate count of elements
    for (int j : arr)
      count[(j / 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 = size - 1; i >= 0; i--) {
      output[count[(arr[i] / place) % 10] - 1] = arr[i];
      count[(arr[i] / place) % 10]--;
    }

    System.arraycopy(output, 0, arr, 0, size);
  }

  // Main function to implement radix sort
  void radixSort(int[] arr) {

    boolean isNegative = false;
    for (int i : arr) {
      if (i < 0) {
        isNegative = true;
        break;
      }
    }

    int min = 0;
    if (isNegative) {
      min = Arrays.stream(arr).min().getAsInt();
      for (int i = 0; i < arr.length; i++) {
        arr[i] -= min;
      }
    }

    // Get maximum element
    int max = Arrays.stream(arr).max().getAsInt();

    // Apply counting sort to sort elements based on place value.
    for (int place = 1; max / place > 0; place *= 10)
      countingSort(arr, place);

    for (int i = 0; i < arr.length; i++) {
      arr[i] += min;
    }
  }
Code language: Java (java)

The implementation and test-cases can also be found on Github.

Video Explanation: