Doubt is a killer. You just have to know who you are and what you stand for.
~Jennifer Lopez

Count Sort

Welcome back readers!

We hope that you are able to exploit free sources of Pep-Coding.

Here we will discuss about next sorting algorithm i.e. "Count Sort". It is better in terms of time complexity than the previously discussed sorting algorithms. It is mainly used when the range of input array doesn't vary much and data is large like say in a competitive exam of 100 marks 100000 students appeared. In such a situation the range is 100 but 100000 is the n(length of the array). How do we do that? We will soon look into it.

So alike in all sorting algorithms you will be given an input array of integers. You have to sort the given array in increasing order using count sort.

For example:

Sample Input: (5, 7, -2, 4, 1, 3)

Sample Output: (-2, 1, 3, 4, 7)

Approach :

First of all let's understand WHAT needs to be done.

Step 1: Scan the given array (arr[]) and identify the minimum and maximum element. In this case minimum value is 3 and maximum value is 9.

Step 2: Then we build a frequency array (farr[])of length range. We define range as the difference of maximum element and minimum element, plus 1 i.e. 7 in this case ((9-3)+1), in order to store the frequency of each distinct value of arr[] in farr[]. Also to be noted, farr[0] corresponds to the frequency of the first and minimum element of range i.e. 3 in this case and so on for the entire farr[].

Step 3: Now we will again travel the original array arr[], so that we can count the frequency of distinct elements and update that in farr[].

Step 4: When we are done with storing the frequencies of each element in farr[], we need to replace these frequencies with cumulative frequency at each index moving from index 0 to last and convert this farr[] into a prefix sum array.

Step 5: We define a new answer array ans[], where we will store our stable and sorted array. For doing that we need to travel the original array arr[], in reverse order. While traveling arr[], whenever we are at any particular element, we look for count in the prefix sum array corresponding to that element. We decrement that count by 1 and use that value as our index for that particular element which we are visiting in the original array. And store that particular element at this index in ans[].

Watch this part of the video for clearing your confusion and to understand this in a better way.

You might think that, after step 3, we could have simply printed our output array by applying for loop on each element and printing it for frequency times. But that is not a stable way of doing it. And if we do it that way then this will not become the Stable Sort.

But, what exactly is stable sort?

Let us say that there are 6 students with corresponding marks and when we sort them according to marks, the one with least marks will go first in the list but what if two or more students get the same marks. Then, who gets to go first in the list?

Yes right, the one who appears first in the list.

Watch this part of the video for clearing your confusion and to understand this in a better way.

Let's try to code this using the signature of this sort, present on the IDE of this question on our website. In this signature we are given both min and max of the input array. Thank God!

Using both these values, we find range and using range we find length of our frequency array, farr[].

Then we define our frequency array and fill farr[] by traversing arr[] and as soon as we are at arr[i], we increment corresponding frequency count (i.e. farr[arr[i] - min]++) in farr[].

Then we convert this frequency array into a prefix sum array, which stores the count of all the smaller elements plus the count of elements to which it's corresponding to.

Then we define an answer array, ans[] of the same length as of arr[]. And fill that while we traverse arr[] in reverse order. We use the element of arr[] as data for ans[] and count the prefix sum array corresponding to this element with a decrement of 1 as index to store that data in ans[]. We also need to decrement the frequency count of the prefix sum array corresponding to this element so that next time we visit it we store this value at a unique position.

After filling our ans[] array in a stable and sorted way, we copy these values in similar order, to our original array[].

Yes! We are finally done.

Watch this part of the video for clearing your confusion and to understand this in a better way.

import java.io.*;
import java.util.*;
public class Main {
public static void countSort(int[] arr, int min, int max) {
int range = max - min + 1;
int[] ans = new int[arr.length];
//make frequency arr
int[] farr = new int[range];
for(int i = 0 ; i < arr.length; i++){
farr[arr[i] - min]++;
}
//convert it into prefix sum array
for(int i = 1 ; i < farr.length; i++){
farr[i] += farr[i - 1];
}
//stable sorting(filling ans array)
for(int i = arr.length - 1; i >= 0; i--){
int pos = farr[arr[i] - min] - 1;
ans[pos] = arr[i];
farr[arr[i] - min]--;
}
//filling original array with the help of ans array
for(int i = 0 ; i < arr.length; i++){
arr[i] = ans[i];
}
}
public static void print(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
public static void main(String[] args) throws Exception {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int[] arr = new int[n];
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
arr[i] = scn.nextInt();
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
countSort(arr,min,max);
print(arr);
}
}

java;
true";

Analysis

Time Complexity :

O(n+k)

We travelled arr[] and farr[] two times.

(n+k) + (n+k) =2 (n+k)

which can be expressed as O(n+k)

SPACE COMPLEXITY :

O(n+k)

Two arrays one farr[] of k length and another ans[] of n length were used.

It would be a pleasure if this article was even 1% helpful to you.

Our desire to make you learn will remain unsatisfactory if you still have doubts. We strongly recommend you to watch our video lecture on Count Sort for clearing any type of doubts.

Suggestions and feedback are always welcomed. You can contact us via our website.

Just don't give up, there is a lot to come. This is merely the beginning.