Radix Sort | Sorting and Searching | C++ Solution
Radix Sort, is a Sorting and Searching related problem and in this post we will see how we can solve this challenge in C++
radix sort In this it sorts the elements acc. to their digits say the max value has 4 digits ,then it will sort all acc. to first 1s place using count sort in linear time then for 10s place ,100s place and so on so TC: O(d * (n + b)) b = base n = num of elements d = no. of digits now d = log base b (k) where k is the max value TC: O( logb(k) * (n + b)) we set k <= n^c and base b = n then Tc :O(n) So if given an array with max value in n^c and base n then we can use this sort
Please check the main.cpp snippet for the solution.
This solution originally posted at: Github by @susantabiswas