JavaScript Sorting Algorithms Explained: Counting Sort -

Today in our JavaScript Sorting Algorithm series we dissect Counting Sort.

We will mention yet another non-comparison sorting algorithm in this series, and that is Counting Sort. Somewhat similar to Radix Sort, Counting Sort has its own limitations and criteria, but when those criteria are met Counting Sort might be the most efficient algorithm for sorting certain (or specific) inputs.

Introduction to Counting Sort

First of all – let us mention the cases that make Counting Sort really efficient. Counting sort blows other sorting algorithms out of the water when the following criteria are met.

When the input array only consists of integers
When the minimum and maximum values in the input array are known beforehand

How and why? Counting sort is based on a simple premise. We have a basic supplementary array that stores the count of each element/number in the input array. Every index in that array has a starting value of 0. Then we loop through the input array and increase the appropriate count by 1 each time we encounter the number in the input array. After the algorithm finishes storing each value in the appropriate index, we loop through the supplementary array and print out the results, which is actually the complete, sorted array!

Visualization

We will implement this algorithm using this input array: [2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2].

Counting Sort Algorithm, for more algorithm visualizations please check visualgo.net

You can imagine that the supplementary array serves the same function as the buckets in Radix Sort. We are looping through the input array and increasing the number index of our supplementary array every time that number appears in the input array. After we iterated through the whole array we just print out the contents of the supplementary array.

Counting Sort Pseudocode and Implementation

The algorithm creates the auxiliary/supplementary array and sets every index to 0
The algorithm should loop through the input array
Every time a certain number is encountered in the input array the index of that number in the supplementary array increases by 1
The algorithm should loop through the supplementary array
For every index count, the algorithm should print out the number of elements
The algorithm should return the sorted list

function countingSort(arr, min, max) {
    let j = 0;
    let supplementary = [];
    
    for (let i = min; i <= max; i++) {
        supplementary[i] = 0;
    }
    
    for (let i=0; i < arr.length; i++) {
        supplementary[arr[i]] += 1;
    }
       
    for (let i = min; i <= max; i++) {
        while (supplementary[i] > 0) {
            arr[j++] = i;
            supplementary[i] -= 1;
        }
    }
    return arr;
}

countingSort([2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2], 1, 9);

We provided our input array, the minimum value in the input array, and the maximum value in the input array as the parameters to the countingSort method.

In the first loop we fill in the supplementary array that we created with zeroes.

In the second loop we loop through the input array and we increase the index of our supplementary array every time we encounter the index in our input array!

Supplementary array with filled indices.

In the third loop we iterate through our supplementary array, and for every count of indices, we create a new loop that will ‘pop’ those values, and insert them in the input array. (Taking a look at the image above – the j value is 0, and we have two values at the index 1. The algorithm will then make two loops, push 1 at the first place in the input array, increase j by one, and then push 1 again to the input array, this time at the increased index, and continue with the same logic until the loop finishes).

Big O complexity

As we can see, this can work only in specific cases – when the array length is not larger than the number of distinct indices or when we know the smallest and the largest number in the input array (we could also retrieve those values using some built-in JavaScript methods inside the body of the function). This algorithm only uses simple for loops, and because of that, we see that the algorithm will take O(k + n) time to finish (iterating n times through the input array and iterating k times through the supplementary array).

Conclusion

Although counting sort is applicable only in some specific situations, it a pretty efficient sorting algorithm. If you want to read a more detailed explanation of the history, assumptions, or the complex analysis of the algorithm click here.

Additionally, if you liked this “JavaScript Sorting Algorithm: Counting Sort” post you can check other sorting algorithms by clicking on them below:

Facebook Tweet Pin LinkedIn