Last Updated: 28 Mar, 2021
Ninja's task
Moderate
Asked in companies
Ninja’s teacher has given him a task to sort a list of the numbers containing N numbers. But the teacher has added the condition that as the range of the numbers in the list is limited, he must do this task in linear time complexity.
Your task is to help Ninja to complete the task.
Example
If n = 10 and nums = [1, 6, 0, -1, 9, 4, 32, 76, -98, 3], then the sorted list would be [-98, -1, 0, 1, 3, 4, 6, 9, 32, 76].
Input Format
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.
The first line of the input contains an integer ‘N’ denoting the number of elements in the list.
The next line contains N space-separated integers denoting the elements in the list.
Output Format
For each test case return the sorted list.
Note:- You don’t need to take input or print anything. This already has been taken care of. Just implement the function.
Constraints:
1 <= T <= 100
1 <= N <= 5000
-10^3 <= nums[i] <= 10^3, where 0<=i<N-1
Approaches
Approach:
In count sort first, we find the number of the object with the specific key values, similar to what we do in hashing.
Then we will find the position of each object in the output.
Algorithm:
- Take an array numCount of size equal to the range of elements of a given array.
- Now store the occurrence of each element in the numCount array but Subtract the minimum element of the given array from every element of the numCount array such that any negative index becomes positive.
numCount[a[i] - min]+=1; where ‘a’ is the given array and min is the minimum element in the given array.
- Modify the numCount array such that each element in the array is equal to the sum of the current value and the previous value.
numCount[i] = numCount[i] + numCount[i-1].
- Now numCount indicates the position of the element in the array.
- Place each element in the ans array as index calculated and after placing the element, decrease its count by one.
ans[numCount[a[i] - min] - 1] = a[i];