Counting Sort Algorithm In Javascript

Learn what is Counting sort and how to implement the Counting sort algorithm in javascript. We will be using it to sort Positive, Negative integers as well as strings.

List of sorting algorithms

What is counting sort?

Counting sort is an integer sorting algorithm, which is used for sorting a collection of elements according to the keys that are small integers.

It sorts the array of elements by counting the frequency of each unique element in the array. The count is stored in another temporary array at the number’s index and using arithmetic on those frequencies to determine the positions of each key value in the sorted array.

Example

Input:
[1, 3, 2, 8, 5, 1, 5, 1, 2, 7]

Output:
[1, 1, 1, 2, 2, 3, 5, 5, 7, 8]

As this algorithm uses the input as the index (like hashing) to store the number of frequency in the temporary array, we cannot perform counting sort on anything using other data structures like linked lists.

Counting Sort Algorithm in Javascript

How counting sort algorithm works?

1. Find out the maximum element from the array and store it in a variable say k.
2. Create a temporary array of the length of the maximum + 1 element and fill 0 at each index.
3. Store the frequency of each element in the array at that element’s index in the temporary array.

For example: if the count of element 1 is 3 then, 3 is stored in the 1st position of the temporary array. If the element is not present in the array, then 0 will be already present there as the default value.

4. Store the cumulative sum of the elements of the temporary array. It helps in placing the elements into the correct index of the sorted array.

e.g. At each index store its frequency + the frequency of its previous index.

Counting Sort counting cycle

5. Find the index of each element of the original array in the temporary array. This gives the cumulative count. Place the element at the index calculated as shown in the below image.

Counting Sort Output Cycle

6. After placing each element at its correct position, decrease its count by one.

countingSort(array, size)
  max <- find largest element in array
  initialize count array with all zeros
  for j <- 0 to size
    find the total count of each unique element and 
    store the count at jth index in count array
  for i <- 1 to max
    find the cumulative sum and store it in count array itself
  for j <- size down to 1
    restore the elements to array
    decrease count of each element restored by 1

Counting sort algorithm on an array of positive integers.

const countingSort = (inputArr, n = inputArr.length) => {
  let k = Math.max(...inputArr);
  let t;
  //Create a temporary with 0 zero value 
  //as the same length of max elemet + 1
  const temp = new Array(k + 1).fill(0);
  
  //Count the frequency of each element in the original array
  //And store it in temp array
  for(let i = 0; i < n; i++){
    t = inputArr[i];
    temp[t]++;
  }

  //Update the count based on the previous index
  for(let i = 1; i <= k; i++){
    // Updating elements of count array 
    temp[i] = temp[i] + temp[i - 1];  
  }
  
  //Output arr
  const outputArr = new Array(n).fill(0);
  
  for(let i = n - 1; i >= 0; i--) {
    // Add elements of array A to array B
    t = inputArr[i];
    outputArr[temp[t] - 1] = t;  
        
    // Decrement the count value by 1
    temp[t] = temp[t] - 1;		
   }
  
  return outputArr;
}

Input:
const arr = [1, 3, 2, 8, 5, 1, 5, 1, 2, 7];
console.log(countingSort(arr));

Output:
[1, 1, 1, 2, 2, 3, 5, 5, 7, 8]

Time complexity

There are basically 5 loops running one after another (after find the max element). Thus we can check the time complexity of each one.

Loop	Time
1st	Θ(max)
2nd	Θ(size)
3rd	Θ(max)
4th	Θ(size)
5th	Θ(size)

Overall complexity = O(max) + O(size) + O(max) + O(size) + O(size) = O(max + size)

Worst	Average	Best
O(max + size)	O(max + size)	O(max + size)

In all the above cases, the complexity is the same because no matter how the elements are placed in the array, the algorithm goes through n+k times.

Space complexity

The space complexity of Counting Sort is O(max). The larger the range of elements, the larger is the space complexity.

Pros & Cons of Counting sort algorithm

There is no comparison between any elements, so it is better than comparison based sorting techniques. But, it is bad if the integers are very large because the array of that size should be made.

Counting sort on array of negative integers

While sorting negative integers we face certain road blocks with counting sort because there are no negative array indices. So what we do is, we find the minimum element and we will store count of that minimum element at zero index.

const countingSortNegative = (arr, n = arr.length) => {
  let max = Math.max(...arr);
  let min = Math.min(...arr);
  let range = max - min + 1;
  let count = new Array(range).fill(0);
  let output = new Array(n).fill(0);
  
  //Store the frequency
  for (let i = 0; i < n; i++) { 
    count[arr[i] - min]++; 
  } 
 
  //Accumulate the frequency
  for (let i = 1; i < count.length; i++) { 
    count[i] += count[i - 1]; 
  } 
  
  //Sort based on frequency
  for (let i = n - 1; i >= 0; i--) { 
    output[count[arr[i] - min] - 1] = arr[i]; 
    count[arr[i] - min]--; 
  } 
  
  return output;
}

Input:
const arr = [-5, -10, 0, -3, 8, 5, -1, 10];
console.log(countingSortNegative(arr));

Output:
[-10, -5, -3, -1, 0, 5, 8, 10]

Sorting an array of characters using counting sort algorithm in Javascript.

Same as the negative numbers, we cannot use characters the array indexes, but we get the ASCII value of the characters as an index and the sort them and covert those ASCII value back to the characters.

const countingSortStr = (str) => {
  let arr = str.split("");
  let n = str.length;
  const output = new Array(n);
  
  // Create a count array to store count of inidividul 
  // characters and initialize count array as 0
  const count = new Array(256).fill(0);
  
  // store count of each character 
  for (let i = 0; i < n; i++){ 
      count[arr[i].charCodeAt()]++; 
  }
  
  // Change count[i] so that count[i] now contains actual 
  // position of this character in output array 
  for (let i = 1; i <= 255; i++){
      count[i] += count[i - 1]; 
  }
  
  // Build the output character array 
  // To make it stable we are operating in reverse order. 
  for (let i = n - 1; i >= 0; i--) { 
      output[count[arr[i].charCodeAt()] - 1] = arr[i].charCodeAt(); 
      --count[arr[i].charCodeAt()]; 
  } 
  
  //Convert the ASCII Value to characters again
  return output.map(e => String.fromCharCode(e));
}

Input:
console.log(countingSortStr("learnersbucket"));

Output:
"abceeeklnrrstu"