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.
- 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.
- 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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
package com.kkjavatutorials.client; import java.util.Arrays; /** * Java Program for Counting sort * @author KK JavaTutorials */ public class CountingSortTest { public static void main(String[] args) { //Input Array int[] inputArr = {0, 4, 5, 6, 5, 4, 8, 9, 8, 6}; //Set input range Max element + 1 int range = 10; System.out.println("Original Input Array:" + Arrays.toString(inputArr)); inputArr = countingSort(inputArr, range); System.out.println("Array Sorted After Counting Sort:" + Arrays.toString(inputArr)); } private static int[] countingSort(int[] inputArr, int range){ int[] outputArr = new int[inputArr.length]; int[] countArr = new int[range]; /*Count number of times each element appear * appear in input array */ for(int i = 0; i < inputArr.length; i++){ countArr[inputArr[i]]++; } //print Count Array System.out.println("Count array:" + Arrays.toString(countArr)); /*Now in count array each element stores * (sum of element at current index + element at previous index) */ for(int i = 1; i < range; i++){ countArr[i] = countArr[i] + countArr[i-1]; } System.out.println("Modified count: " + Arrays.toString(countArr)); for(int i = 0; i < inputArr.length; i++){ outputArr[countArr[inputArr[i]] - 1] = inputArr[i]; countArr[inputArr[i]]--; } return outputArr; } } |
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.