Last Updated: 25 Oct, 2021

Counting Sort

Easy

Asked in companies

Solve now

Problem statement

Ninja is studying sorting algorithms. He has studied all comparison-based sorting algorithms and now decided to learn sorting algorithms that do not require comparisons.

He was learning counting sort, but he is facing some problems. Can you help Ninja implement the counting sort?

For example:

You are given ‘ARR’ = {-2, 1, 2, -1, 0}. The sorted array will be {-2, -1, 0, 1, 2}.

Input Format:

The first line contains an integer 'T' which denotes the number of test cases.

The first line of each test case contains an integer ‘N’ representing the length of the ‘ARR’ array.

The second line of each test case contains ‘N’ space-separated integers representing the ‘ARR’ array.

Output Format:

For each test case, print the sorted array.

The output of each test case will be printed in a separate line.

Constraints:

1 <= T <= 10 
1 <= N <= 5000
-10^4 <= ARR[i] <= 10^4

Time limit: 1 sec

Note:

You do not need to input or print anything, as it has already been taken care of. Just implement the given function.

Solve now

Approaches

01 Approach

As the name suggests, counting sort is a sorting technique that counts the frequency of every unique element in the array, and this frequency is used in mapping to an index of a temporary array taken for sorting.

But since the input array also contains negative numbers, we can not map their frequency to an index. So, to overcome this problem, we will first find the minimum element, and instead of mapping the frequency of ‘ARR[I]’ to index ‘ARR[I]’, we will map the frequency to index ‘ARR[I]’ - 1.

Suppose ‘ARR’ = {-3, 1, 0 -1}.

MInimum element = -3.

After subtracting the minimum element from each element of ‘ARR’:

‘ARR’ = {0, 4, 3, 2}.

Now, we can easily map the frequency of every element to an index.

Algorithm:

Initialize a variable 'MAX' to store the maximum element of the input array.
Initialize a variable 'MIN' to store the minimum element of the input array.
Iterate 'I' in 0 to 'N':
- Set 'MAX' as the maximum of 'MAX' and 'ARR[I]'.
- Set ‘MIN’ as the minimum of 'MAX' and 'ARR[I]'.
Set 'RANGE' as 'MAX' - 'MIN' + 1.
Initialize an array 'COUNT' of size 'RANGE'.
Initialize an array 'ANS' of size 'N'.
Iterate 'I' in 0 to 'N':
- Increment 'COUNT[ARR[I] - MIN]' by 1.
Iterate 'I' in 1 to 'COUNT.LENGTH':
- Set 'COUNT[I]' as 'COUNT[I]' + 'COUNT[I - 1]'.
Iterate 'I' in 'N - 1' to 0:
- Set 'ANS[COUNT[ARR[I] - MIN] - 1]' as 'ARR[I]'.
- Decrement 'COUNT[ARR[I] - MIN]' by 1.
Finally, return 'ANS'.

Solve now