Counting Sort: Why, When, & How
Sorting is a near ubiquitous process in our daily lives. It makes sense to organize things to better use them. The same can be said for data. In computer programming—and mathematics, for that matter—sorting algorithms are frequently used to order data as needed to perform a calculation, feed an engine, render an interface, etc.
There are several well known sorting algorithms: e.g. bubble, quick, selection, insertion, merge, heap, bucket. There is also a lesser known sorting algorithm, relegated to the proverbial annex like poor Toby: counting sort. Have you ever heard of it? It is infrequently used because it comes with some caveats which make it impractical in most use cases. However, if the stars align and the conditions are just right, counting sort offers a unique advantage: it is the only sorting algorithm which performs in linear time (O(n)).
Most sorting algorithms perform in quadratic time (O(n²)), and the two exceptions—heap and merge—maximize efficiency at linearithmic time (O(n log n)). Counting sort provides a rarely useable, but more performant algorithm. If the conditions allow, and time efficiency is a priority, counting sort can shine.
*Note: linear time sorting can also be achieved with the best case scenario bucket sort (which is not a proper evaluation—time complexity considers the worst case scenario) and radix sort, which itself utilizes counting sort as a sub-routine.
Caveat #1: Positive Integers Only
Unlike most other sorting algorithms, counting sort is not a comparison sort. It is an integer sort. The sorting is performed by using values concurrently as keys and indices. This requires a condition wherein the objects—the elements, or values—being sorted are exclusively integers, and, since they must be able to represent an Array index, they must be 0 or greater.
Caveat #2: Lesser Values
As the name suggests, counting sort utilizes a counting procedure. It is in the form of an auxiliary Array which stores the frequency count, i.e. number of occurrences, of each value. It is done by initializing an Array of 0s to accommodate the maximum input value. For example, if the input was the sequence 5 1 3, the count Array would need to accommodate an index 5, plus an additional element to represent the index 0.
input => 5 1 3count Array => idx 0 1 2 3 4 5
______________________
arr [0, 0, 0, 0, 0, 0]
This condition requires that the maximum value of the integers being sorted is a relatively small number. The need to create an auxiliary Array comes at the cost of space, and if the maximum input value is great, then the space complexity of the algorithm would make it inefficient and, therefore, unusable.
I presume an acceptable maximum value is circumstantial, but once large numbers (1000+?) enter the mix, consider an alternative algorithm. Note that the specific time complexity of counting sort is O(n + k), wherein n is the length of the input, and k is the range of the input. It’s simpler to think of k, the range, as the maximum value of the input.
Algorithm: In JavaScript
There are numerous variations of the counting sort algorithm. I’m going to share one that I wrote. It’s possibly not the best one, but it works and is rudimentary, understandable. Two commonalities that I’ve noticed in other examples are 1) the need to know the minimum and maximum values to include as input, and 2) the use of a while loop nested within a for loop. My variation allows for inputting only an Array of integers, and does not have nested loops. Perhaps a trade off considering my example has slightly “worse” space complexity, but it’s fun to try different things.
Mechanics:
function countingSort(arr) {// initialize count Array: 0 * (arr max value + 1(for index 0)) const countArr = new Array(Math.max(...arr) + 1).fill(0)// initialize accumulation Array with one element: 0
// this will be used to store key values as an index legend const accumulationArr = [0]// initialize accumulator to aid construction of accumulation Array let accumulator = 0// initialize sorted Array for result: 0 * arr.length const sortedArr = new Array(arr.length).fill(0)// load the count Array by tracking occurrences
// of each unique value in the input Array // loop over elements of the input Array
for (const i of arr) {
// access matching index of count Array and
// increment the corresponding value by 1
countArr[i]++
}// load the accumulation Array by accumulatively adding
// the values of the count Array, in sequence, to create
// an index legend for the pending sorting procedure
// note that the accumulation Array already contains the
// value 0 at index 0, and the loop stops before the last
// accumulation as it is not needed for calculations for (let i = 0; i < countArr.length - 1; i++) {
// the accumulator is assigned the value of the first element
// of the count Array on the first iteration, then on, the
// accumulative value of previous elements + current element
accumulator += countArr[i]
// the current accumulator value is added to
// the accumulation Array
accumulationArr.push(accumulator)
}// load the sorted result Array by looping over the input Array,
// using the current element to access an index from the
// accumulation Array, accessing that index in the sorted Array
// and assigning it the value of the current elementfor (let i = 0; i < arr.length; i++) {
// assign the index variable the value from the
// accumulation Array at [index = current element]
let index = accumulationArr[arr[i]]
// use the index variable to assign value from input Array
// to correct position in sorted Array
sortedArr[index] = arr[i]
// increment the value from the accumulation Array
// at [index = current element] by 1 to shift target index
// by 1 to accommodate pending repeated input values
accumulationArr[arr[i]]++
}// output the sorted result Array console.log(sortedArr)
return sortedArr
}
Example:
// input
const arr = [5, 1, 4, 4, 3, 2]// function
function countingSort(arr) {
const countArr = new Array(Math.max(...arr) + 1).fill(0)
// countArr => [0, 0, 0, 0, 0, 0] const accumulationArr = [0]
// accumulationArr => [0] let accumulator = 0
// accumulator => 0 const sortedArr = new Array(arr.length).fill(0)
// sortedArr => [0, 0, 0 ,0, 0, 0] for (const i of arr) {
countArr[i]++
}
// countArr => [0, 1, 1, 1, 2, 1]////// explanation /////////////////////////////////////////////////
————————————————————————————————————————————
input | 5 1 4 4 3 2 |
____________________________________________
countArr | 0 1 2 3 4 5 | (indices)
____________________________________________
loop 1 | 0 0 0 0 0 1 | 1 occurrence of 5
loop 2 | 0 1 0 0 0 1 | 1 occurrence of 1
loop 3 | 0 1 0 0 1 1 | 1 occurrence of 4
loop 4 | 0 1 0 0 2 1 | 2 occurrence of 4
loop 5 | 0 1 0 1 2 1 | 1 occurrence of 3
loop 6 | 0 1 1 1 2 1 | 1 occurrence of 2 for (let i = 0; i < countArr.length - 1; i++) {
accumulator += countArr[i]
accumulationArr.push(accumulator)
}
// accumulationArr = [0, 0, 1, 2, 3, 5]////// explanation /////////////////////////////////////////////////
_______________________________________________
loop 1 | countArr = [0, 1, 1, 1, 2, 1,]
| accumulator = 0 + 0
| accumulationArr = [0, 0]
———————————————————————————————————————————————
loop 2 | countArr = [0, 1, 1, 1, 2, 1,]
| accumulator = 0 + 1
| accumulationArr = [0, 0, 1]
———————————————————————————————————————————————
loop 3 | countArr = [0, 1, 1, 1, 2, 1,]
| accumulator = 1 + 1
| accumulationArr = [0, 0, 1, 2]
———————————————————————————————————————————————
loop 4 | countArr = [0, 1, 1, 1, 2, 1,]
| accumulator = 2 + 1
| accumulationArr = [0, 0, 1, 2, 3]
———————————————————————————————————————————————
loop 5 | countArr = [0, 1, 1, 1, 2, 1,]
| accumulator = 3 + 2
| accumulationArr = [0, 0, 1, 2, 3, 5] for (let i = 0; i < arr.length; i++) {
let index = accumulationArr[arr[i]]
sortedArr[index] = arr[i]
accumulationArr[arr[i]]++
}////// explanation /////////////////////////////////////////////////
______________________________________________
loop 1 | accumulationArr = [0, 0, 1, 2, 3, 5]
| index = 5
| sortedArr = [0, 0, 0, 0, 0, 5]
| accumulationArr = [0, 0, 1, 2, 3, 6]
————————————————————————————————————————————––
loop 2 | accumulationArr = [0, 0, 1, 2, 3, 6]
| index = 0
| sortedArr = [1, 0, 0, 0, 0, 5]
| accumulationArr = [0, 1, 1, 2, 3, 6]
————————————————————————————————————————————––
loop 3 | accumulationArr = [0, 1, 1, 2, 3, 6]
| index = 3
| sortedArr = [1, 0, 0, 4, 0, 5]
| accumulationArr = [0, 1, 1, 2, 4, 6]
————————————————————————————————————————————––
loop 4 | accumulationArr = [0, 1, 1, 2, 4, 6]
| index = 4
| sortedArr = [1, 0, 0, 4, 4, 5]
| accumulationArr = [0, 1, 1, 2, 5, 6]
————————————————————————————————————————————––
loop 4 | accumulationArr = [0, 1, 1, 2, 5, 6]
| index = 2
| sortedArr = [1, 0, 3, 4, 4, 5]
| accumulationArr = [0, 1, 1, 3, 5, 6]
————————————————————————————————————————————––
loop 4 | accumulationArr = [0, 1, 1, 3, 5, 6]
| index = 1
| sortedArr = [1, 2, 3, 4, 4, 5]
| accumulationArr = [0, 1, 2, 3, 5, 6] console.log(sortedArr)
return sortedArr
}// output
// sortedArr => [1, 2, 3, 4, 4, 5]
Solution:
function countingSort(arr) {
const countArr = new Array(Math.max(...arr) + 1).fill(0)
const accumulationArr = [0]
let accumulator = 0
const sortedArr = new Array(arr.length).fill(0)
for (const i of arr) {
countArr[i]++
}
for (let i = 0; i < countArr.length - 1; i++) {
accumulator += countArr[i]
accumulationArr.push(accumulator)
} for (let i = 0; i < arr.length; i++) {
let index = accumulationArr[arr[i]]
sortedArr[index] = arr[i]
accumulationArr[arr[i]]++
} console.log(sortedArr)
return sortedArr
}
That’s a lot of text to take in, and there is still some ambiguity as to precisely why this works, but like a Stanley Kubrick or David Lynch film, this article is meant to present you with an introduction, a plot, and a finale—not the deeper meaning. While I’ve included ample demonstration, I encourage you to search around the internet and play around with counting sort to fully grasp the process to your own understanding. Everyone learns differently. At the very least, you have an overview, a foundation, and an example to study and use.
github.com/dangrammer
linked.com/in/danieljromans
danromans.com
