In this post, we will learn how to implement Counting Sort in java. First, we will start by understanding the Counting Sort algorithm.
Counting Sort Algorithm
Counting Sort Algorithm is an integer-based algorithm, non-comparison, and linear sorting algorithm. The counting sort algorithm sorts the elements in an array in a specific range. It is based on keys between the specific range.
Counting sort calculates the number of occurrences of objects and stores their key values. Then by adding the previous key elements, a new array is formed.
Before we begin, you need to have an idea on following:
Time Complexity of Counting Sort:
- Best case:
0(n+k) - Average case:
0(n+k) - Worst case:
0(n+k)
Implementation of Counting Sort in java
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 | import java.util.Arrays; public class CountingSortJava { public static void main(String[] args) { int[] arr = { 5, 34, 3, 2, 34, 3, 5, 2, 5, 34, 6, 2 }; int k = 34; System.out.println("Array before sorting"); System.out.println(Arrays.toString(arr)); countingSortFn(arr, k); System.out.println("Array after Counting sorting: "); System.out.println(Arrays.toString(arr)); } public static void countingSortFn(int[] input, int k) { // creating buckets int counter[] = new int[k + 1]; // filling buckets for (int i: input) { counter[i]++; } // sorting int ndx = 0; for (int i = 0; i < counter.length; i++) { while (0 < counter[i]) { input[ndx++] = i; counter[i]--; } } } } |
The output of Counting sort algorithm in java:
