**by BehindJava**

# Data Structures - Counting Sort Algorithm

In this tutorial, we are going to learn about counting sort in detail and its algorithmic implementation.

# Counting Sort

- Not an in-place algorithm.
- O(n) - can achieve this because we’re making assumptions about the data we’re sorting.
- If we want the sort to be stable, we have to do some extra steps.
- Makes Assumptions about the data.
- Doesn’t use comparisons.
- Counts the number of occurrences of each value.
- Only works with non-negative discrete values(cant work with floats, Strings).
- Values must be within a specific range.

- Assume we have values between 1 to 10 inclusive.
- We have 10 possible values, so we create a counting array of length 10.
- Traverse the input array from left to right.
- Use the counting array to track how many of each value are in the input array.
- Using the counts in the counting array, write the values in sorted order to the input array.

# Counting Sort Algorithm

- countingSort(array, size)
- max <- find largest element in array
- initialize count array with all zeros
- for j <- 0 to size.

find the total count of each unique element and store the count at jth index in count array - for i <- 1 to max.

find the cumulative sum and store it in count array itself - for j <- size down to 1.

restore the elements to array decrease count of each element restored by 1.

# Counting Sort Programmatic Implementation in Java

```
public class CountingSort {
public static void main(String[] args) {
int[] intArray = { 2, 5, 9, 8, 2, 8, 7, 10, 4, 3 };
countingSort(intArray, 1, 10);
for (int i = 0; i < intArray.length; i++) {
System.out.print(intArray[i]+ " ");
}
}
public static void countingSort(int[] input, int min, int max) {
int[] countArray = new int[(max - min) + 1];
for (int i = 0; i < input.length; i++) {
countArray[input[i] - min]++;
}
int j = 0;
for (int i = min; i <= max; i++) {
while (countArray[i - min] > 0) {
input[j++] = i;
countArray[i - min]--;
}
}
}
}
```

Output:

`2 2 3 4 5 7 8 8 9 10 `