Select Page

Counting Sort in Java

The sorting technique that uses counting (the frequency of occurrence of elements) to do the sorting is called counting sort. The counting sort uses the frequency of elements as value and the element as key. Hence, counting sort resembles the hashing technique. Counting sort in Java implements the hashing technique between the frequency of occurrence of the elements and the element itself.

Algorithm & Pseudo Code

Java Program
The following code implements the Counting sort using the pseudo-code defined above.

FileName: CountingSortExample.java

Output:

Explanation: Finding the maximum value element of the input array is the key here. The size of the array countArr[] is one more than the value of the maximum value element.

It is done because we have to ensure that while storing the count of the elements, the program never gives ArrayIndexOutOfBoundsException. Now the frequency of the elements present in the input array is collected in the array countArr[]. The following diagram illustrates the same.

After this, the cumulative sum of the countArr[] array is found. By doing this, we ensure the location of the elements in the sorted array. At this point, we have all the information to sort the input array, i.e., the frequency of elements and their location. The following diagram shows the same.

Now, the elements are arranged in proper sequence in the outcome[] array. After that, the array copied to the array a[].

### Handling negative numbers in the input array

There is a serious issue that is lurking in the code that is written above. The issue is if there are some negative numbers are present in the input array, the above code fails to work, as indices are always non-negative. The following Java program resolves the issue.

FileName: CountingSortExample1.java

Output:

Explanation: The key is to find the range with the help of the minimum and maximum value elements present in the input array. The range determines the size of the countArr[] array. Doing subtraction by the minimum value element is the key to avoid ArrayIndexOutOfBoundsException while storing the frequency of occurrence of elements in countArr[]. The rest of the logic is still the same as the previous example.

Analysis of Counting Sort

Counting sort is a stable sorting algorithm that does the sorting by imitating the concept of hashing. As hashing does not compare elements, the same is true for the counting sort. Hence, this sorting algorithm is also no comparison sorting algorithm.

Time Complexity

The counting sort algorithm never used nested loops to do the sorting, and the same is evident in the above code. In the first example, we can only see the linear loops.

The countArr[] array can only have maxEle + 1 elements. Thus, the linear iteration on the countArr[] takes O(maxEle) times. There are two for-loops that iterates on the elements of countArr[], making the time complexity O(maxEle) + O(maxEle). However, we have additional loops too in the code, one of which does the copying of element from the array outcome[] to the input array[], taking O(n) times, where n is the total number of elements present in the input array.

Another loop in the getMax() method finds the maximum value element in O(n) times. Again, another for-loop deal with the frequency of elements of the input array in O(n) times.

Thus, overall time complexity becomes O(maxEle) + O(maxEle) + O(n) + O(n) + O(n) which is asymptotically represented by O(n + maxEle).

Note that the frequency of occurrence of an element never depends upon the arrangement of elements in an array. Therefore, the counting sort treats a sorted or an unsorted array, in the same manner, making the time complexity of O(n + maxEle) for the best, worst, and the average case scenario.

Space Complexity

We have used two auxiliary arrays while doing the sorting. One array is outcome[] array whose size is equal to the size of the input array, making the space complexity O(n), where n is the total number of elements present in the array.

Another array is countArr[], whose size is one more than the maximum value element of the input array, which makes the space complexity O(maxEle  + 1).

Thus, overall space complexity is O(n) + O(maxEle + 1) that is asymptotically represented by O(n + maxEle).

In the best, worst, or the average cases, the overall space complexity of the counting sort remains the same, i.e., O(n + maxEle).

Conclusion

Counting sort is one of those sorting algorithms that take linear time to sort an array. It is better than other sorting algorithms because it takes quadratic time O(n^2) or logarithmic time O(n logn) to do the sorting.

However, the downside of this sorting algorithm is if the range of elements present in the input array is large, the memory allocation of elements becomes extremely high, which may lead to the memory leak. Let’s understand it with the help of an example.

If the input array is a[] = {45556, 13, 890, 5}; Then memory allocation occurs for 45557 elements to sort only four elements. Thus overall, the memory is 45557 * 4 = 182228 bytes of memory which is extremely large. Therefore, it is not advisable to go with counting sort when the data is of higher range. For this reason, it is not widely used.