# Counting Sort in Java - Algorithm

Categories:
Viewed: 106 - Published at: a year ago

### Introduction

Sorting is one of the fundamental techniques used in solving problems, especially in those related to writing and implementing efficient algorithms.

Usually, sorting is paired with searching - meaning we first sort elements in the given collection, then search for something within it, as it is generally easier to search for something in a sorted, rather than an unsorted collection, as we can make educated guesses and impose assumptions on the data.

There are many algorithms that can efficiently sort elements, but in this guide we'll be taking a look at how to implement Counting Sort in Java.

### Counting Sort in Java

Counting Sort is a stable, non-comparative sorting algorithm, and it's main use is for sorting arrays of non-negative integers. Counting Sort counts the number of objects that have distinct key values, and then applying a prefix sum on those counts to determine the position of each key in the output. Like all other non-comparative sorting algorithms, Counting Sort also performs the sort without any comparisons between the elements to be sorted. Also, being a stable sorting algorithm, Counting Sort preserves the order of the elements with equal keys sorted in the output array as they were in the original array. This operation results in, essentially, a list of integer occurrences, which we typically name the count array. Counting Sort uses the auxilliary count array to determine the positions of elements: Each index in the count array represents an element in the input array. The value associated with this index is the number of occurrences (the count) of the element in the input array. The best way to get a feel of how Counting Sort works is by going through an example. Consider we have an array:

``````int[] arr = {0, 8, 4, 7, 9, 1, 1, 7};
``````

For simplicity's sake, the elements in the array will only be single digits, that is numbers from `0` through `9`. Since the largest value we can have is `9`, let's label the maximum value as `max = 9`. This is important because we'll need to designate a new count array, consisting of `max + 1` elements. This array will be used for counting the number of occurrences of every digit within our original array we're given to sort, so we need to initialize the whole count array to `0`, that is:

``````int[] countArray = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
``````
Since there are 10 possible elements our array can have, there are ten zero's for every single digit.

Since we've defined the array we'll be working on, and we have also defined our count array to keep count of each occurrence of a digit, we need to go through the following step to make Counting Sort work: Step 1: By going through our whole array `arr` in a single `for` loop, for every `i` from `0` to `n-1`, where `n` is the number of elements in `arr`, we'll count the occurrence of each digit by incrementing the value on the position `arr[i]` in our `countArray`. Let's see that in code:

``````for(int i = 0; i < arr.length; i++)
countArray[arr[i]]++;
``````

After the first step, our `countArray` looks like this: [1, 2, 0, 0, 1, 0, 0, 2, 1, 1]. Step 2: Since we now have our `countArray` filled with values, we go on to the next step - applying prefix sums to the `countArray`. Prefix sums are basically formed when we add each of the previous numbers in the array onto the next accumulatively, forming a sum of all yet seen prefixes:

``````for(int i=1; i < countArray.length; i++)
countArray[i] += countArray[i-1];
``````

And after applying this step we get the following `countArray`: [1, 3, 3, 3, 4, 4, 4, 6, 7, 8]. Step 3: The third and last step is calculating the element positions in the sorted output based off the values in the `countArray`. For this purpose, we'll need a new array that we'll call `outputArray`. The size of the `outputArray` is the same as our original `arr`, and we once again initialize this array to all zeros:

``````int[] outputArray = {0, 0, 0, 0, 0, 0, 0, 0};
``````

As we've mentioned earlier, Counting Sort is a stable sort. If we iterated through our `arr` array from `0` to `n-1` we may end up switching the elements around and ruin the stability of this sorting algorithm, so we iterate the array in the reverse order. We'll find the index in our `countArray` that is equal to the value of the current element `arr[i]`. Then, at the position `countArray[arr[i]] - 1` we'll place the element `arr[i]`. This guarantees we keep the stability of this sort. Afterwards, we decrement the value `countArray[i]` by one, and continue on doing the same until `i >= 0`:

``````for(int i = arr.length-1; i >= 0; i--){
outputArray[countArray[arr[i]] - 1] = arr[i];
countArray[arr[i]]--;
}
``````

At the end of the algorithm, we can just copy the values from `outputArr` into our starting array `arr` and print the sorted array out:

``````for(int i = 0; i < arr.length; i++){
arr[i] = outputArray[i];
System.out.print(arr[i] + " ");
}
``````

Running of course gives us the sorted array with guaranteed stability (relative order) of equal elements:

``````0 1 1 4 7 7 8 9
``````

### Complexity of Counting Sort

Let's discuss both the time and space complexity of Counting Sort. Let's say that `n` is the number of elements in the `arr` array, and `k` is the range of allowed values for those `n` elements from `1...n`. As we're working only with simple `for` loops, without any recursive calls, we can analyze the time complexity in a following manner:

• Counting the occurrence of each element in our input range takes `O(n)` time,
• Calculating the prefix sums takes up `O(k)` time,
• And calculating the `outputArray` based off the previous two takes `O(n)` time.

Accounting for all the complexities of these individual steps, the time complexity of Counting Sort is `O(n+k)`, making Counting Sort's average case linear, which is better than most comparison based sorting algorithms. However, if the range of `k` is `1...n²`, the worst-case of Counting Sorts quickly deteriorates to `O(n²)` which is really bad. Thankfully, this doesn't happen often, and there is a way to ensure that it never happens. This is how Radix Sort came to be - which typically uses Counting Sort as its main subroutine while sorting. By employing Counting Sort on multiple bounded subarrays, the time complexity never deteriorates to `O(n²)`. Additionally, Radix Sort may use any stable, non-comparative algorithm instead of Counting Sort, but it's the most commonly used one.

On the other hand, the space complexity problem is much easier. Since our `countArray` of size `k` is bigger than our starting array of `n` elements, the dominating complexity there will be `O(k)`. Important thing to note is that, the larger the range of elements in the given array, larger is the space complexity of Counting Sort.