Radix Sort

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
9 upvotes
Asked in companies
MicrosoftAmazon

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
4
1 4 3 5
5 
5 4 3 2 1
Sample Output 1 :
1 3 4 5
1 2 3 4 5
Explanation Of Sample Input 1 :
In test case ‘1’, ‘1 3 4 5’ is the increasing sorted order.
In test case ‘2’. ‘1 2 3 4 5’ is the increasing sorted order.
Sample Input 2 :
2
2
30 25
6 
2 2 2 2 2 2
Sample Output 2 :
25 30
2 2 2 2 2 2
Hint

 What happens in the counting sort?

Approaches (1)
Radix Sort

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 : 

  1. Calculate the maximum element in the input array ‘arr’.
  2. Initialise the pow10 is equal to '1'.
  3. We will iterate over all digits from the '0th' position to the maximum pow of the 10th position.
  4. 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’.

Time Complexity

O( N * log10( max(ARR) ) ), Where 'N' is the number of elements in the array and max(ARR) is the maximum element in array 'ARR'.

 

We are doing the counting sort which takes ~O(N)  for the number of digits that is (log10( max(v) ) times.

Hence, the time complexity is O( N * log10( max(ARR) ) ).

Space Complexity

O(N), Where ‘N’ is the size of the vector
 

We are using another vector to store ~N element in sorted order and then copying it to the given vector.

Hence the space complexity is O(N).

Code Solution
(100% EXP penalty)
Radix Sort
Full screen
Console