Counting Sort Algorithm 101

Here we go with another sort algorithm implemented in JavaScript!

Photo by Djim Loic on Unsplash

How the Counting Sort Algorithm Works

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

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;
}

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;
};

Conclusion

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store