the TC of this question is O(n) in Worst Case so how to solve this hint and approach…
How to approach counting sort
hi @mohit26900
In this problem, we do not use comparisons instead we use a frequency array to sort the array. This can be done using first calculating the frequency of each element that occurs in the array and then printing an element till its frequency is greater than zero. The size of the frequency array will be the max-min+1, where max and min are the maximum and minimum of the array respectively. For every occurring element e, increase frequency at index e by 1. For an array with negative elements also, we consider the size as max-min+1 where minimum has its absolute values considered. The index 0 of the frequency array will now represent the minimum value of the array. So we can store the values on the correct index by considering that index=element-min. While again printing the original value in the sorted array is by saying that the value is index+min value as it was altered while storing on the correct index. 1) Take a count array to store the count of each unique object. 2) Modify the count array such that each element at each index stores the sum of previous counts.The modified count array indicates the position of each object in the output sequence. 3) Output each object from the input sequence followed by decreasing its count by 1. Time and Space Complexities: The time complexity of the algorithm is O(n+k), where n is the number of elements and k is the range of input.The space complexity is also the same. Since a frequency is needed to store the frequency.
Required Code for counting sort is given below :
is frequency array stores elements in increasing order…
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.