Implementing Counting Sort with JavaScript

David Inoa — Tue, 13 Aug 2019 02:05:23 +0000

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

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.

(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.

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

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

(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.

(6) Return your sorted array.

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).

DEV Community: David Inoa

Implementing Counting Sort with JavaScript

Implementation

Breakdown

Complexity