DEV Community

David Inoa
David Inoa

Posted on

Implementing Counting Sort with JavaScript

Counting sort is an algorithm that, in certain cases, allows you to sort an array in linear time. To use counting sort your array must only contain integers, and it is assumed you know the minimum and maximum values.

Implementation

counting sort algorithm

Breakdown

(1) Create a new array counts in which you will keep track of how many times an integer is present in your input array. The length of counts will be determined by the range of the values in your input array. Each index in counts will correspond to an integer, and each value at this particular index will tell us how many times the integer is present in our input.

code fragment

(2) If all our integers are positive, we could just keep track of the count for each one at the index in counts corresponding to its value (i.e. counts[3] is where we save our count for an integer 3). But for this algorithm to work with negatives, we must determine an offset value to helps us map both negative and positive integers to an index in counts.

code fragment

(3) Populate counts by iterating through your original array. Every time we encounter an integer, we increase its count by one.

code fragment

(4) Initialize an array to hold the integers in ascending order.

code fragment

(5) Loop through all the integers between your min and max. At each iteration, determine the count for the current integer. If the count is 0, we continue to the next one. But if the count is greater than 0, we push that integer to sortedIntegers as many times as indicated by count.

code fragment

(6) Return your sorted array.

code fragment

Complexity

In the worst-case scenario, the complexity of this algorithm is as follows:

  • Time complexity: O(n + k), where n is the numbers of integers in your original array and k is the range of your min and max values.
  • Space complexity: O(n + k)

When k is less or equal to n, both complexities reduce to O(n).

Top comments (1)

Collapse
 
joynal profile image
Joynal Abedin

Hi David, Thanks for your article. Did you test your implementation with negative and duplicate values? It's not working for the negative value. If you increase array index with an additional offset you should also increase auxiliary array size. In step one you need const counts = new Array(max + min).fill(0); instead of const counts = new Array(max - min + 1).fill(0);