Counting Sort in JAVA

Counting Sort

There is a detailed explanation in the book In troduction to Algorighms, Third Edition and Wikipedia.

Counting Sort owns O(k+n) time complecity in average, while k is the size of total number we could use to sort and n is the size of unsorted array.

We need at list three array to complete the sort. input array, count array and output array.

For simplicity, assume the input data in the range 0 to 9.
Input data: 2, 5, 3, 0, 2, 3, 0, 3
1) Take a count array to store the count of each unique object.
Index: 0 1 2 3 4 5 6 7 8 9
Count: 2 0 2 3 0 1 0 0 0 0

2) Modify the count array such that each element at each index
stores the sum of previous counts.
Index: 0 1 2 3 4 5 6 7 8 9
Count: 2 2 4 6 7 8 8 8 8 8

The modified count array indicates the position of each object in
the output sequence.

3) Output each object from the input sequence followed by
decreasing its count by 1.

Code

The simple code is following:

Leave a Reply

Your email address will not be published. Required fields are marked *