CountSort.java

importjava.util.Arrays;
importjava.util.Scanner;

publicclassCountSort {

publicstaticvoidmain(String[] args) {

// This algorithm is preferred for single digit number
System.out.println("Counting Sort : ");

System.out.print("Enter the size of array : ");
try (Scannersc = newScanner(System.in)) {
intn = sc.nextInt();
inta[] = newint[n];

System.out.println("Enter elements : ");
for (inti = 0; i < n; i++) {
a[i] = sc.nextInt();
 }

System.out.println("Array before sorting : " + Arrays.toString(a));

countSort(a); // calling the function

System.out.println("\nArray after sorting : " + Arrays.toString(a));
 }

// Time Complexity : O(n+k+n+n) = O(n+k) 
// if we consider k as content then O(n) -> Linear Time :)
// Space Complexity : O(n+k)
 }

privatestaticvoidcountSort(inta[]) {
intk = getMax(a); // to get maximum element for making count array

intcount[] = newint[k + 1]; // to fill frequency of element
for (inti = 0; i < a.length; i++) {
count[a[i]]++;
 }

// to reflect position in count array
// similar to filling cumulative frequency 
for (inti = 1; i <= k; i++) {
count[i] = count[i] + count[i - 1];
 }

// to put element at it's correct position
intb[] = newint[a.length];
for (inti = b.length - 1; i >= 0; i--) {
b[--count[a[i]]] = a[i];
 }

// copying elements to a
for (inti = 0; i < a.length; i++)
a[i] = b[i];
 }

privatestaticintgetMax(int[] a) {
intmax = Integer.MIN_VALUE;
for (inti : a) {
if (i > max)
max = i;
 }
returnmax;
 }
}