Last Updated: 15 Apr, 2022

Radix Sort

Moderate

Asked in companies

Solve now

Problem statement

Ninja is given an array of integers ‘ARR’ of size ‘N’. He has to sort the given array in increasing order using radix sort.

Ninja called you for help as you are his only friend. Help him to solve the problem.

Example :

Input: ‘N’ = ‘4’ ,  'V' = [ 2 , 1 , 4 , 3 ] 

Output: "1 2 3 4"

As [ 1 , 2 , 3 , 4 ] is the sorted order.

Input Format :

The first line will contain the integer 'T', denoting the number of test cases.

For each test case, the first line contains a single integer ‘N’ the size of the input array.

Second-line contains ‘N’ space-separated integers which are the elements of the input array.

Output format :

For each test case, print the element of the array input array in increasing order.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= 'T' <= 10
1 <= ‘N’ <= 10^4
1 <= ARR[i] <= 10^9
Time Limit: 1 sec

Solve now

Approaches

01 Approach

In, Radix Sort we do digit by digit sorting. We start from the least significant digit to the most significant digit. Radix sort uses counting sort as a subroutine to sort.

Let's see how the counting sort works.

Suppose ‘ARR’ is the input array.
First, we make the 10 sized ‘BIN’ array for the ‘10’ different digits at a position for different numbers.
And now we will increase the count of the bin according to the digit.
Now we will iterate over the bin array so that at the ith position we can get how many numbers are smaller than it.
After that, we will create another array ‘TEMP’ and store values of array ‘ARR’ in sorted order in ‘TEMP’ by using the ‘BIN’ array that gives the number of elements smaller than it. Then coping ‘TEMP’ to ‘ARR’.

This we will do for all positions in a number(from least significant to most significant).

The steps are as follows :

Calculate the maximum element in the input array ‘arr’.
Initialise the pow10 is equal to '1'.
We will iterate over all digits from the '0th' position to the maximum pow of the 10th position.
For each iteration:
- Calling the helper function ‘countingSort’ to sort the array based on pow10'th digit.
- Inside the Helper function ‘countingSort’ :
  - Initializing the temporary array to all zeros.
  - Creating a '10' sized ‘bin’ named array to store the count of the element according to the pow10'th digit.
  - Storing value in the bin[i] such that bin[i] will represent the number whose pow10'th digit is smaller than 'i'.
  - Adding elements in the 'temp' array using the 'bin' array.
  - Calculate the pow10'th digit of the number and check-in bin array how many elements are smaller than it.
  - Return the 'temp' array and copy it to the array ‘arr’

6. Return ‘arr’.

Solve now