He that can have patience can have what he will.
~ Benjamin Franklin

Radix Sort

Welcome back readers!

We hope that you are able to exploit free sources of Pep-Coding.

Here we will discuss about next sorting algorithm i.e. "Radix Sort". It is better in terms of time complexity than the previously discussed sorting algorithms. It is really important that you have already gone through Count Sort before you jump to this one.

It is mainly used when the range of input array doesn't vary much and data is large like say in a competitive exam of 100 marks 100000 students appeared. In such a situation the range is 100 but 100000 is the n(length of the array). How do we do that? We will soon look into it.

Problem Discussion :

So alike in all sorting algorithms you will be given an input array of integers.

You have to sort the given array in increasing order using radix sort.

For example:

Sample Input: (5, 7, -2, 4, 1, 3)

Sample Output: (-2, 1, 3, 4, 7)

Approach :

First of all let's understand WHAT needs to be done. Consider an input array which is shown in the first column of the image.

Step 1: Scan the given array (arr[]) and sort it on the basis of unit place using stable count sort. After doing this, the array looks like column 2 of the image.

Step 2: Then we sort it on the basis of tens place using stable count sort. After doing this, the array looks like column 3 of the image.

Step 3: And finally on the basis of the hundredth place using stable count sort. After doing this, the array looks like column 4 of the image.

Why finally? Well because in the above example our maximum value is of 3 digit only i.e. up to hundredth place only.

Watch this part of the video for a clearer and better understanding of this part.

Let's try to code this using the signature of this sort, present on the IDE of this question on our website.

If you have already visited our website and gone through the signature which is already mentioned in the code editor then you will find that in addition with the signature of radix sort, you are also given the signature of count sort.

Why?

As in the starting of the article I told you that it is very important to know about Count Sort before you move to Radix Sort. That is because, while coding for Radix Sort, we will be using Count Sort.

So here we will not understand the code of Count Sort and just use it directly from the previous article.

But we need to edit the code of Count Sort as the code which we saw in previous article was applicable on complete numbers rather than any single digit of that number but when we rearrange these digits, and then complete numbers are taken into consideration.

Also, the digits will only vary from 0 to 9 therefore the range will be 10.

Now we will solve our problem of processing only digits into count sort and still managing to consider the entire number while sorting. This part will be tackled using Radix sort.

For that, first of all we find the maximum element of the array.

Then we run a for loop for exp (exponential) which decides how many times our loop will run and call Count Sort.

In easy language it will make calls equal to the number of digits in maximum value.

But how? Well the condition and updating part of the for loop helps us do that. After each iteration, we multiply our exp with 10 and it runs until the maximum value on division with exp gives a value greater than 1.

And wherever we use farr[arr[i]-min], we will replace this with farr[arr[i] / exp % 10] as our digit varies only from 0 to 9 and we want to sort our array on the basis of digit at a particular place.

Yes! We are finally done.

Watch this part of the video for clearing any confusion and to understand this in a better way.

import java.io.*;
import java.util.*;
public class Main {
public static void radixSort(int[] arr) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
}
//call countSort for every digit from right to left
for (int exp = 1; max / exp >= 1; exp *= 10)
countSort(arr,exp);
}
public static void countSort(int[] arr, int exp) {
int[] ans = new int[arr.length];
// make frequency arr
int[] farr = new int[10];
for (int i = 0; i < arr.length; i++) {
farr[(arr[i]/exp) % 10]++;
}
// convert it into prefix sum array
for (int i = 1; i < farr.length; i++) {
farr[i] += farr[i - 1];
}
// stable sorting(filling ans array)
for (int i = arr.length - 1; i >= 0; i--) {
int pos = farr[(arr[i]/exp) % 10] - 1;
ans[pos] = arr[i];
farr[(arr[i]/exp) % 10]--;
}
// filling original array with the help of ans array
for (int i = 0; i < arr.length; i++) {
arr[i] = ans[i];
}
System.out.print("After sorting on " + exp + " place -> ");
print(arr);
}
public static void print(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) throws Exception {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = scn.nextInt();
}
radixSort(arr);
print(arr);
}
}

java;
true";

Analysis

Time Complexity :

O(bn)

We call count sort b times(b being the number of digits in maximum value). And the time complexity of count sort is O(n+k) but k is constant(10) here. So it becomes bO(n) or O(bn).

SPACE COMPLEXITY :

O(n+b)

It would be an extreme pleasure if this article was helpful to you.

Our desire to make you learn will remain unsatisfactory if you still have doubts. We strongly recommend you to watch our video lecture on Radix Sort for clearing any type of doubts.

Suggestions and feedback are always welcomed. You can contact us via our website.

Just don't burden yourself; there is a lot more to come. This is merely the beginning. Don't give up.