Counting Sort Algorithm 101

Here we go with another sort algorithm implemented in JavaScript!

Photo by Djim Loic on Unsplash

Ok, so I have to admit, I really like this algorithm. It’s not the fastest sorting algorithm, nor is it the most efficient. But I happen to love the fact that this algorithm doesn’t compare values in a list to produce an ordered result! That’s right, the counting sort algorithm takes a conceptual left-turn and approaches this fundamental problem from different angle. This approach exemplifies the kind of creative thinking that drew to me to programming in the first place.

Before we dig into the specifics I think it’s important to note that this solution and its implementations are strongly related to the idea of hash tables. So before you jump into the code below, make sure you have a general understanding of how hash tables work and are implemented in JavaScript (it will make everything a lot clearer as you move on).

Here is a resource to refresh and/or describe how they work:

A Great Guide to Hash-Tables in JavaScript by Rohan Paul (pay special attention to the function that removes duplicates from an array) —

Algorithms in JavaScript: Hash Tables

How the Counting Sort Algorithm Works

From a high level, the Counting Sort Algorithm (CSA) sorts a list of unsorted integers just like any other sorting algorithm. But unlike many commonly used algorithms, the CSA does not actually compare elements in the list against each other to determine their place in the sorted result.

Instead, the CSA creates a new list containing all of the elements (from the smallest to the largest integer found in the input array) and assigns a value to each of them that represents the number of times that element appears in the input array.

For this to work properly, we have to know what the minimum and maximum values are in the array are before we execute the algorithm. That’s right, our countingSort function is going to take 3 arguments:

1. The unsorted input array.
2. The smallest number found in the array.
3. The largest number found in the array.

Ok, that may have been a little confusing to grasp on the first read. So let’s run through a more visual example to clear up the details.

Input array --> [2,3,0,5];
Smallest Number in the array --> 0;
Largest Number in the array --> 5;
We create a loop that starts at the smallest Number and ends at the largest Number. This loop creates a new array with 6 elements.
The newly created 'COUNT' array has 6 elements [0,0,0,0,0,0] with indexes [0,1,2,3,4,5];
Then we loop over the input array and use each element from that array as an index for the newly created 'COUNT' array.
1. Start the loop over the input array
2. Element at index [0] with value [2]
3. If the 'COUNT' array with index [2] exists
4. Add 1 to the value at index [2] in the 'COUNT' array
Repeat this pattern for the whole array...
Updated Count Array:
Indexes -> [0,1,2,3,4,5]
Values --> [1,0,1,1,0,1]
We then use the updated COUNT array to re-populate the input array in sorted order.
The last loop in this implementation uses the integers from the smallest number to the larger number.
We use those values in the 'COUNT' array and for each element with a value greater than 0, we add that integer to the beginning of the original array from smallest to greatest.
This results in an updated array that looks like this 
--> [0,2,3,5];

Implementation

Now we are going to implement the CSA into JavaScript code using 2 iterative approaches. The first implementation uses three loops to achieve the goal and closely resembles the explanation above. The second implementation is a slight variation, but overall the same approach.

First Implementation

const countingSort = (array, minimumValue, maximumValue) => {
  // We declare an iterator and an array to hold the total number
  // of each value found in the input array  
  let z = 0;
  let count = [];
  // Adds the exact number starting from the minimumValue 
  // to the maximumValue into the count array (each with 
  // a value of 0)
  for (let i = minimumValue; i <= maximumValue; i++) {
    count[i] = 0;
  };
  // Loop through the count array and for each element
  // with an index === to the input array, we add 1 
  for (let i = 0; i < array.length; i++) {
    count[array[i]] += 1;
  };
  // Loop from the minimumValue to the maximumValue,
  // while the count includes an index found in between minValue 
  // and maxValue - 1, is greater than 0,
  // we replace the value at array[with index z] 
  // (z starts at 0), with the element at value i
  // and then iterate z forward
  for (let i = minimumValue; i <= maximumValue; i++) {
    while (count[i]-- > 0) {
      array[z] = i;
      z++;
    }
  }
  return array;
}

Second Implementation

This implementation is essentially the same as the one above with one significant difference. In this implementation we create the count array without using a loop. There is also a little trick used in the code below to deal with negative integers…

Hint: Array indexes can’t be negative, how does the code below get around this problem?

const countingSort2 = (array, minimumValue, maximumValue) => {
  // Create a temp array with a length equal to max - min, 
  // with placeholder values of 0
  const count = new Array(maximumValue - minimumValue + 1).fill(0);
  // Create a variable that returns the minimumValue as 
  // an absolute (positive) number
  const indexBalancer = Math.abs(minimumValue);
  
  // Create an empty array for sorted numbers  
  const sortedArray = [];
  // We loop through the input array
  // For each number from the input array found in
  // the count array, we increment its value by 1
  // But this can't be achieved using negative numbers!
  // Therefore we use the indexBalancer to increase the 
  // indexes of all numbers so they are > -1
  // Here is an example: count[-3 + 5] --> count[2] = 1 
  // (we have found 1 instance of the number -3 in the 
  // input array and placed it at index 2 in the count array)
  for (let number of array) {
    count[number + indexBalancer]++
  }
  // For each value in range, we get the tally for that
  // value in the count array
  // This loop goes from smallest to greatest
  for (let i = minimumValue; i <= maximumValue; i++) {
    let tally = count[i + indexBalancer];
    
    // while the tally is > 0, push the element into the
    // sortedArray and reduce the tally by 1
    while(tally > 0) {
      sortedArray.push(i);
      tally--;
    }
  }
  return sortedArray;
};

Both implementations achieve the same result by slightly different means. The largest difference between the 2 implementations is how they create an empty count array at the beginning of the function. They also approach the process of pushing values (from smallest to largest) into a sortedArray variable with slightly different methods.

I encourage anyone trying to wrap their head around the CSA to run both implementations and console.log() each variable to understand how they change over time.

Conclusion

So that was the Counting Sort Algorithm implemented in JavaScript. From an efficiency stand point the CSA has a time-complexity of O(n + k). The n represents the number of elements to be sorted and the k represents the range between the minimum and maximum values found in the unsorted array.

Generally speaking, you won’t see the CSA used where the range (k) exceeds the number of elements to be sorted (n). If the range exceeds the unsorted elements, then we create a potentially huge count array that will increase the time-complexity drastically, even if the unsorted array only contains 5 elements. If k is less than or equal to n then the the time-complexity is basically reduced to O(n). Basically, you should only be using this if you can achieve O(n) time-complexity.

Here is a list of sources that helped me wrap my head around the Counting Sort Algorithm and will definitely help you solidify your understanding further:

My Github Repo of the CSA implementations in JavasScript —

twjsanderson/countingSort

An Awesome Article on the Counting Sort Array by Vaidehi Joshi —

Counting Linearly With Counting Sort

A Straight Forward Guide on the Counting Sort Algorithm from Interview Cake —

Counting Sort Algorithm | Interview Cake

That’s it, thanks for reading!

A note from JavaScript In Plain English

We have launched three new publications! Show some love for our new publications by following them: AI in Plain English, UX in Plain English, Python in Plain English — thank you and keep learning!

We are also always interested in helping to promote quality content. If you have an article that you would like to submit to any of our publications, send us an email at submissions@plainenglish.io with your Medium username and we will get you added as a writer. Also let us know which publication/s you want to be added to.