Problem Link :–
Author :- Ranjan Kumar
Editorialist :- Ranjan Kumar
Difficulty
medium
Pre-Requisites :
sorting, queue.
Problem Statement :-
The problem is to sort N non-negative random numbers in non -decreasing order using Radix Sort Technique.
Detailed Approach :–
As the question is very straight forward and standard one, it will be the best to put the standard explanation for the question and not putting my own idea.
So I am putting the approach stated by Geeks For Geeks (which is also mentioned in the question).
Operations which are performed in Radix Sort is as follows:-
1) Do following for each digit i where i varies from least significant digit to the most significant digit.
………….a) Sort input array using counting sort (or any stable sort) according to the i’th digit.
Example
Original Unsorted List
170, 45, 75, 90, 802, 24, 2, 66
Sorting by least significant digit (1s place) gives: [*Notice that we keep 802 before 2, because 802 occurred before 2 in the original list, and similarly for pairs 170 & 90 and 45 & 75.]
170, 90, 802, 2, 24, 45, 75, 66
Sorting by next digit (10s place) gives: [*Notice that 802 again comes before 2 as 802 comes before 2 in the previous list.]
802, 2, 24, 45, 66, 170, 75, 90
Sorting by most significant digit (100s place) gives:
2, 24, 45, 66, 75, 90, 170, 802
Hence we get a sorted sequence for the corresponding random sequence.
Time Complexity :–
O(N*K)
where N - Size of array.
K - Number of digits in the largest number.
Solution :–
Setter’s Solution can be found here
Feel free to post comments if anything is not clear to you.