# Radix Sort in Java - Java

Categories:
Viewed: 58 - Published at: 6 months ago

### Introduction

Sorting is one of the fundamental techniques used in solving problems, especially in those related to writing and implementing efficient algorithms.

Usually, sorting is paired with searching - meaning we first sort elements in the given collection, then search for something within it, as it is generally easier to search for something in a sorted, rather than an unsorted collection, as we can make educated guesses and impose assumptions on the data.

There are many algorithms that can efficiently sort elements, but in this guide we'll be taking a look at how to implement Radix Sort in Java.

### Radix Sort in Java

Radix Sort is a non-comparative sorting algorithm, meaning it doesn't sort a collection by comparing each of the elements within it, but instead relies on something called the radix to sort the collection.

The radix (often called the base) is the number of unique digits in a positional numeric system, used to represent numbers.

For the well-known binary system, the radix is 2 (it uses only two digits - 0 and 1). For the arguably even more well-known decimal system, the radix is 10 (it uses ten digits to represent all numbers - from 0 to 9).

How does Radix Sort use this to its advantage?

Radix Sort doesn't sort by itself, really. It uses any stable, non-comparative sorting algorithm as its subroutine - and in most cases, the subroutine is Counting Sort. If `n` represents the number of elements we are to sort, and `k` is the range of allowed values for those elements, Counting Sort's time complexity is `O(n+k)` when `k` is in range from `1...n`, which is significantly faster than the typical comparative sorting algorithm with a time complexity of `O(nlogn)`.

But the problem here is - if the range is `1...n²`, the time complexity drastically deteriorates to `O(n²)` very quickly.

The general idea of Radix Sort is to sort digit by digit from the least significant ones to the most significant (LSD Radix Sort) and you can also go the other way around (MSD Radix Sort). It allows Counting Sort to do its best by partitioning the input and running Counting Sort multiple times on sets that don't let `k` approach `n²`. Because it's not comparison based, it's not bounded by `O(nlogn)` - it can even perform in linear time. Since the heavy lifting is done by Counting Sort, let's first go ahead and take a look at how it works and implement it, before diving into Radix Sort itself!

#### Counting Sort in Java - Theory and Implementation

Counting Sort is a non-comparative, stable sorting algorithm, and it's main use is for sorting arrays of integers.

The way it works is, it counts the number of objects having distinct key values, and then applying a prefix sum on those same counts to determine the position of each key value in the output. Being stable, the order of records with equal keys is preserved when the collection is sorted. This operation results in, essentially, a list of integer occurrences, which we typically name the count array. Counting Sort uses the auxilliary count array to determine the positions of elements: Each index in the output array represents an element in the input array. The value associated with this index is the number of occurences (the count) of the element in the input array. The best way to show how Counting Sort works is through an example. Consider we have the following array:

``````int[] arr = {3, 0, 1, 1, 8, 7, 5, 5};
``````

For the sake of simplicity, we'll be using digits from 0 through 9. The maximum value of a digit we can take into consideration is obviously 9, so we'll set a `max = 9`. This is important because we need an additional, auxilliary array consisting of `max + 1` elements. This array will be used to count the number of appearances of every digit within our array `arr`, so we need to initialize the whole counting array `countingArray` to `0`.

``````int[] countingArray = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
// there are 10 digits, so one zero for every element
``````

Now that we've both defined the array we'll be working with and initialized the counting array, we need to do the following steps to implement Counting Sort: 1. Traversing through our `arr` array, and counting the occurrence of every single element while incrementing the element on the position `arr[i]` in our `countingArray` array:

``````for(int i = 0; i < arr.length; i++)
countingArray[arr[i]]++;
``````

After this step, `countingArray` has the following elements: `[1, 2, 0, 1, 0, 2, 0, 1, 1, 0]`. 2. The next step is applying prefix sums on the `countingArray`, and we get the following:

``````for(int i=1; i < countingArray.length; i++)
countingArray[i] += countingArray[i-1];
``````

After the modification of the counting array it now consists of `countingArray = {1, 3, 3, 4, 4, 6, 6, 7, 8, 8}`. 3. The third and last step is to calculate element positions in the sorted output based of the values in `countingArray`. For that we'll need a new array that we'll call `outputArray`, and we'll initialize it to `m` zeros, where `m` is the number of elements in our original array `arr`:

``````int[] outputArray = {0, 0, 0, 0, 0, 0, 0, 0};
// there are 8 elements in the arr array
``````
Since Counting Sort is a stable sorting algorithm, we'll be iterating through the `arr` array in reverse order, lest we end up switching the elements.

We'll find the index in our `countingArray` that is equal to the value of the current element `arr[i]`. Then, at the position `countingArray[arr[i]] - 1` we'll place the element `arr[i]`. This guarantees the stability of this sort, as well as placing every element in it's right position in the sorted order. Afterwards, we'll decrement the value of `countingArray[i]` by 1. At the end, we'll be copying the the `outputArray` to `arr` so that the sorted elements are contained within `arr` now. Let's unify all of these snippets and completely implement Counting Sort:

``````int[] arr = {3, 0, 1, 1, 8, 7, 5, 5};
int[] countingArray = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

for(int i = 0; i < arr.length; i++)
countingArray[arr[i]]++;

for(int i=1; i < countingArray.length; i++)
countingArray[i] += countingArray[i-1];

int[] outputArray = {0, 0, 0, 0, 0, 0, 0, 0};
for(int i = arr.length-1; i >= 0; i--){
outputArray[countingArray[arr[i]] - 1] = arr[i];
countingArray[arr[i]]--;
}

for(int i = 0; i < arr.length; i++){
arr[i] = outputArray[i];
System.out.print(arr[i] + " ");
}
``````

Running this will give us a sorted array:

``````0, 1, 1, 3, 5, 5, 7, 8
``````

As mentioned earlier, the time complexity of this algorithm is `O(n+k)` where `n` is the number of elements in `arr`, and `k` is the value of `max` element in the array. However, as `k` approaches `n²` this algorithm deteriorates towards `O(n²)`, which is a major downside of the algorithm. Since we've briefly explained how Counting Sort works, let's move on to the main topic of this article - Radix Sort.

#### Radix Sort in Java - Theory and Implementation

Again, Radix Sort typically Counting Sort as a subroutine, so Radix Sort itself is a stable sorting algorithm as well. The keys used by the Counting Sort will be the digits of the integers within the array we're sorting.

There are two variants of Radix Sort - one that sorts from the Least Significant Digit (LSD), and the second one that sorts from the Most Significant Digit (MSD) - we'll be focusing on the LSD approach.

Radix Sort by itself isn't very complicated to understand once we understand how Counting Sort works, so the steps taken to implement it are fairly simple:

1. Find the `max` element in the input array.
2. Determine the number of digits, `d`, the `max` element has. The number `d` represents how many times we'll go through the array using Counting Sort to sort it.
3. Initialize the number `s` to 1 at the beginning, representing the least significant place and working it's value up by multiplying it by 10 every time.
For example, let's say we have the following input array `arr = {73, 481, 57, 23, 332, 800, 754, 125}`. The number of times we'll loop through the array is 3, since the `max` element in our `arr` array is 800, which has 3 digits.

Let's go through a visual example of an array being sorted this way, step by step, to see how Radix Sort sorts the elements in each iteration: The input array is broken down into the digits that make up its original elemments. Then - either using by the most significant digit and working our way down, or the least significant digit and working our way up, the sequence is sorted via Counting Sort: In the first pass, only the right-hand side is used to sort, and this is why stability in Radix Sort/Counting Sort are key. If there was no stability, there would be no point in sorting this way. In the second pass, we use the middle row, and finally - the left-hand row is used, and the array is fully sorted. Finally, let's implement Radix Sort:

``````static void radixSort(int[] arr) {
int max = arr;
for (int i = 1; i < arr.length; i++) {
if (max < arr[i])
max = arr[i];
}

for (int s = 1; max / s > 0; s *= 10)
}
``````

We'll also want to sligthly modify Countinng Sort. This modification of Counting Sort does the exact same thing as the previous implementation, only it focuses on digits in different places of the integers at a time:

``````static void countingSortForRadix(int[] arr, int s) {
int[] countingArray = {0,0,0,0,0,0,0,0,0,0};
for (int i = 0; i < arr.length; i++)
countingArray[(arr[i] / s) % 10]++;

for (int i = 1; i < 10; i++)
countingArray[i] += countingArray[i - 1];

int[] outputArray = {0,0,0,0,0,0,0,0};
for (int i = arr.length - 1; i >= 0; i--)
outputArray[--countingArray[(arr[i] / s) % 10]] = arr[i];

for (int i = 0; i < arr.length; i++)
arr[i] = outputArray[i];
}
``````

Let's create an array and try sorting it now:

``````public static void main(String[] args) {
int[] arr = {73,481,57,23,332,800,754,125};

for (int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " ");
}
``````

This results in:

``````23, 57, 73, 125, 332, 481, 754, 800
``````

Since we are using Counting Sort as the main subroutine, for an array containing `n` elements, that has the `max` element with `d` digits, in a system with a `b` base, we have the time complexity of `O(d(n+b))`. That's because we're repeating the Counting Sort process `d` times, which has `O(n+b)` complexity.

### Conclusion

Although Radix Sort can run very efficiently and wonderfully, it requires some specific cases to do so. Because it requires that you represent the items to be sorted as integers, it's easy to see why some other comparison-based sorting algorithms can prove to be a better choice in many cases. The additional memory requirements of Radix Sort compared to some other comparison based algorithms is also one of the reasons that this sorting algorithm is used more rarely than not. On the other hand, this algorithm performs superbly when the input array has shorter keys, or the range of elements is smaller.

Reference: stackabuse.com