How to write the Counting Sort program in Java ?

By | July 22, 2020

In this post, we will learn How to write the Counting Sort program in Java.

Counting sort is one of the O(n) sorting algorithm like Bucket Sort and Radix Sort. Since it runs in linear time O(n) so counting sort is faster than the comparison-based algorithms like Quick Sort and Merge Sort.

Even though counting sort is one of the fastest sorting algorithms but it has certain drawbacks. One of them is that the range of elements should be known in advance. It also needs auxiliary space as it needs to store the frequency of each element.

How does counting sort work

The way counting sort works by counting the frequency of each element to create a frequency array or count array and then these counts are usually used to compute the index of an element in the sorted array.

  1. To create a count array to store the count of each element. If the range of elements is 0 to m then count array should be of length m+1. For example, if the max element in the array is 20 then count array should be of length 21.
  2. We have to iterate through the elements in the input array and for each element increment its count in the corresponding index in the count array.

           For example, if input array is- [0, 4, 5, 6, 5, 4, 8, 9, 8, 6]

Complete Source Code:

The Output of this Program:

Original Input Array:[0, 4, 5, 6, 5, 4, 8, 9, 8, 6]
Count array:[1, 0, 0, 0, 2, 2, 2, 0, 2, 1]
Modified count: [1, 1, 1, 1, 3, 5, 7, 7, 9, 10]
Array Sorted After Counting Sort:[0, 4, 4, 5, 5, 6, 6, 8, 8, 9]

Performance of Counting Sort:

If the number of elements to be sorted is n and the range of elements is between 0-m then the time complexity of Counting sort can be calculated as-

The loop to create count array takes O(n) time and the second loop where count array is modified takes O(m) time and creating sorted output array again takes O(n) time. So, the time complexity with all these combined together then it comes as O(2n+m). Since constants are not taken into consideration so the time complexity of Counting sort is O(n+m).

The auxiliary space requirement is also (n+m). Count array takes m space and the output array n. Thus, the space complexity of the Counting sort is O(n+m).

You May Also Like:

What is Sorting and why is Sorting Necessary?
Classification of Sorting Algorithms
Java program for Bubble Sort using Iterative Approach
Java program for Bubble Sort using recursive Approach
How to Write a Java program for Selection Sort in Java
How to Write a Java program for Insertion Sort in java?
How to write a Merge sort program in Java
How to write a Quick Sort program in Java
How to write a Radix sort program in Java
Tree Sort Using Binary Search Tree in Java

That’s all about How to write the Counting Sort program in Java?
If you have any feedback or suggestion please feel free to drop in below comment box.

Leave a Reply

Your email address will not be published.