Counting Sort

Easy
0/40
profile
Contributed by
18 upvotes
Asked in companies
Morgan StanleySamsungPayPal

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}.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
5
-2 1 2 -1 0
5
1 2 3 -4 -5
Sample Output 1:
-2 -1 0 1 2
-5 -4 1 2 3
Explanation:
For the first test case, the sorted array will be {-2, -1, 0, 1, 2}.
For the second test case, the sorted array will be {-5, -4, 1, 2, 3}.
Sample Input 2:
2
4
1 3 4 2
4
1 1 -1 -1
Sample Output 2:
1 2 3 4
-1 -1 1 1
Hint

Try to map the frequency of every element to an index.

Approaches (1)
Counting Sort

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'.
Time Complexity

O(N + K), where N is the length of the input array ‘ARR’ and K is the input range. 
 

We are iterating through the input array thrice and the ‘COUNT’ array once. Hence the overall time complexity is O(N + k).

Space Complexity

O(N + K). where N is the length of the input array ‘ARR’ and K is the input range. 
 

The auxiliary arrays ‘ANS’ and ‘COUNT’ will have lengths ‘N’ and ‘K’, respectively. Hence the overall space complexity is O(N + K).

Code Solution
(100% EXP penalty)
Counting Sort
Full screen
Console