package misc;

import java.util.Arrays;

/**

* Counting sort is used to sort elements between specific range.

* Counting sort calculates the number of occurrence of objects and stores its key values.

* New array is formed by adding previous key elements and assigning to objects.

* It can only sort an integer array or number array e.g. short, byte or char array.

*

*/

public class CountingSort {

public static void countingSort(int[] input, int k) {

int counter[] = new int[k + 1];

// fill bucket

for(int i : input) {

counter[i]++;

}

// sort array

int ndx = 0;

for(int i = 0; i < counter.length; i++) {

while( 0 < counter[i]) {

input[ndx++] = i;

counter[i]--;

}

}

}

public static void main(String[] args) {

int[] input = { 60, 40, 30, 20, 10, 40, 30, 60, 60, 20, 40, 30, 40 };

int k = 60;

System.out.println("Integer array before sorting: " + Arrays.toString(input));

countingSort(input, k);

System.out.println("Integer array after sorting: " + Arrays.toString(input));

}

}