If there’s one question that every developer finds themselves asking on a daily basis, it must be this: is it possible to make this better? In almost every context, we seem to ask ourselves some variation of this question. Usually, we’re concerned with finding the solution, then getting it out of our heads and into a text editor, whiteboard, or down on a piece of paper. Eventually, we start transforming that idea into code, and the code is pretty terrible the first time around.
And that’s okay! Kent Beck’s mantra of “Make it work, make it right, make it fast” holds itself to be true for this very reason. But at some point, once we’ve made it work and made it right, we find ourselves asking: can I make it fast? Can I make it better?
I love sorting things, but there’s one glaring problem that I’ve noticed over the past few weeks – and perhaps you’ve noticed it too. It’s really hard to sort efficiently! We’ve learned a lot of different ways to sort things: six different ways, to be exact. Most of them had a quadratic runtime, and a few of them had a linearithmic runtime. But, we’ve never gotten any better than that, have we?
This got me thinking: is it possible to do even better? As it turns out, most of the time, the answer to this question in the context of sorting algorithms is no. It’s nearly impossible to do better than linearithmic runtime, or O(n log n) in Big O Notation. The keyword here is, of course, nearly. Because, every once in awhile, we can do better. And today, we’re finally going to learn how!
Counting sheep! Uh, wait, I mean counting SORT!
As we near the end of our deep-dive into sorting algorithms, we’re going to change gears a bit. We’ve looked a lot of comparison-based sorting algorithms so far, but the last few algorithms we’ll look at are going to be quite different. For starters, they’ll be faster than the ones we’ve been learning about, but they are also limited in how we can use them.
When I say “limited”, what I mean is that we’re limited in what types of elements we can sort using these algorithms. But this will make more sense when we start looking at an example. Let’s start with a definition first!
The first algorithm to wrap our heads around is something called the counting sort algorithm. Don’t be fooled by the name – it’s not nearly as boring and mathematical as it sounds!
The counting sort algorithm is unique in that it can only be implemented on integers. This is part of what limits this algorithm’s usability – and it’s possibly part of the reason that you may have never heard or encountered it before! Counting sort takes in a range of integers to be sorted. It uses the range of the integers (for example, the range of integers between 0–100), and counts the number of times each unique number appears in the unsorted input.
The algorithm leverages the fact that it knows beforehand the range of elements to be sorted, and the fact that all the elements are integers, and builds up a “count” array, which it uses to tally up how many numbers appear in the unsorted collection. It then uses some math and a partial hashing function to map the elements to keys in the duplicated “count” array.
Phew, okay, that was a handful of words to get through. And maybe it didn’t make all that much sense? Don’t worry if it didn’t; I tend to think that counting sort makes very little sense as just a definition. Out of all the algorithms we’ve learned about thus far, I think this one can be the most confusing – unless you see it in action.
Before we sink our heels into an example, let’s quickly cover the key things we should always keep in mind about counting sort.
First and foremost, we should only ever think of using or implementing counting sort if the items we want to sort are all integers.
Second, we need to be sure that we know the range of our input integers. As we’ll see in the next few sections, counting sort leans heavily on knowing the range of the input; if we don’t know how small and how big our input integers are, we can’t really use counting sort.
Third, even if we know the range of our input integers, we still need to think a bit about what our integers are; that is to say, what the range between the smallest input integer and the largest input integer could possibly be. If we had 5 elements to sort, but the range of the input values were between 0 and 10,000, counting sort wouldn’t work that well, since it has to create a “count” array.
These rules are great to know, but they become so much more obvious with an example. So, let’s take a look at one now!
Counting elements as we see them
We know that we can only implement counting sort on an integer input, and we know that the range between these elements should stay pretty small. In our example, which is illustrated below, we’re sorting an array with just eight elements: [9, 4, 1, 7, 9, 1, 2, 0]. Notice that there are some duplicate values, which is totally okay!
In this situation, we know that the data we’re sorting will always range between 0 and 9.
We’ll start by creating the “count array”, which is highlighted in pink. Remember, we’ll need this in order to do the work of tallying up how many of each number (between 0–9) we have in our input data. After we’ve done the work of tallying, we’ll do the work of sorting!
Once we create our “count array”, we will be able to use the indexes of the array to map to the elements themselves. When we initialize our “count array”, every single index starts off with an initial value of 0. Then, we’ll need to do the work of populating our “count array” with the tallied up elements from our unsorted, input array.
So, how are we going to do this, exactly? Well, what we really care about at the moment is just figuring out how many times a single number appears in our input array. In other words, we want to know how many 0’s appear in the array, how many 1’s, how many 2’s, how many 3’s, and so on, until we get to the number 9, which is the last, maximum value in our input array. Doing this work is just about as simple as it sounds: we can iterate through the array and keep count of how many times we’ve seen a certain number, until we’ve iterated through the entire input dataset.
If you’ve read about hash tables and hashing functions, you might already be able to guess how this is going to go. Let’s see if you’re right! In order to make this a bit more obvious, I’ve redrawn the arrays to be vertical, so that we can see the hashing work more clearly:
Cool! Notice how we’re iterating through our unsorted array, and keeping a tallying of how many times we see each number.
For example, the first element that we start with is the number 9. We find index 9 in the count array, which is currently set to 0, and we increment it by one. Then we move on to look at the next element: 4. We find index 4 in the count array, and increment it from 0 to 1. We do the same thing for the next two elements: 1 and 7.
Eventually, we hit another instance of 9. So, we find index 9 in the count array; remember that we already saw an instance of 9, so the value of index 9 in the count array is currently set to 1. But no worries! We have duplicates in this array, and that’s fine – we’ll just increment it from 1 to 2. Problem solved. We can continue on our merry way, until we’ve iterated through the entire input array.
Effectively, as we iterate through the unsorted integer array, we’re counting each element and keeping track of that count at the corresponding index of the “count array” by incrementing the value at the index that maps to the appropriate number.
Great! We now have a count array that is populated with tallies of how many times each number, ranging from 0–9, appears in our unsorted integer array.
The next step involves some math – but don’t worry, it won’t be too difficult! All we need to is accumulatively add each pair of consecutive values in our count array.
For example, we’ll add the element at index 0 to the element at index 1 in our count array. In this case, these two elements are 1 and 2. Since 1 + 2 = 3, we’ll update the index of 1 element to be the sum of the previous element.
We’ll continue to build up our count array by adding the previous index’s value to the next, for the remainder of the array. As we continue to add accumulatively, our count array is transformed as a result.
Our count array now looks like: [1, 3, 4, 4, 5, 5, 5, 6, 6, 8].
Next, we’ll need to shift over our array by one index. In order to do the work of shifting, we can just iterate through our array, and increment the index of each element.
After shifting over our count array by one index, it would look like this:
After shifting, our count array now looks like: [0, 1, 3, 4, 4, 5, 5, 5, 6, 6]. If we think about this a bit more deeply, it starts to (hopefully) make more sense why this step is important. Remember that the value at each index tells us where the first instance of that integer will appear in our sorted array. For example, the value at index 9 in our count array is 6. In other words, this tells us that the first instance of 9 will occur at index 6 of our sorted array. Another way to think about this is that there were be six elements that will appear before the number 9 in our sorted array.
As I discovered through my own trial and error, if we skip this step, our array might still end up in sorted order, but we’ll have one extra element added to it, and it’ll be just slightly off. So we should be particularly careful to not forget the step of shifting!
Okay, we’re down to the last step now: translating our count array into our new, sorted array. The first thing that we’ll do is create a new array that will hold our sorted elements. Once we have that, we can actually start the work of sorting. Let’s look at all three arrays – our original array, our count array, and our new sorted array, as we do this next step.
First, we’ll want to iterate through our original array, and find the index that corresponds to the value we’re looking at. Then, we’ll look at the tallied count at that index.
For example, we start looking at our first element in the original array: 9. We’ll go to our count array, find index 9, and the value at that that index. In this case, it’s the number 6.
We’ll find the index 6 in our new array, and put a 9 there. And finally, we’ll increment the value at the corresponding index in the count array; you can see that I’ve crossed out the number 6 and replaced it with the number 7 in our count array. We do this increment step after we’ve sorted the first instance of the number 9.
We can see how this same step is repeated with the next couple elements in the array, and how each time, as we sort, we increment the number at the corresponding index in the count array. The increment step is crucial in order to be able to sort duplicate values, and in order to maintain the order of those elements as they appear in the unsorted array.
Eventually, if we continue doing this as we iterate through the entire array, we’ll end up with a new, sorted array, that looks like this:
Nice! Our array = sorted. And our situation = handled. Good work, team.
Deconstructing counting sort
Okay, we did a pretty detailed walk through of the counting sort algorithm the previous section! Before we look at a quick code example, let’s review the basic steps of counting sort.
- To start, we must create a “count array”, which we’ll populate by tallying up (or hashing) all the elements in the original array by how many times they appear in the unsorted array.
- Next, we’ll accumulatively add up the values in the populated count array, building it up as we go along.
- Then, we’ll shift over all the elements in the array by incrementing the index of each value by one.
- Finally, we’ll create a new sorted array, which will be the same length as our original array. We’ll iterate over our original array, and translate the values over to our new array by using our count array, incrementing our count array value as we continue to sort. In this step, we’re effectively using a version of a hashing function, and using our count array as a way to translate values from the unsorted array into the new, sorted one.
Okay, let’s see this algorithm in action! Below is an abridged version of Rosetta Code’s JavaScript implementation of counting sort. Remember how I mentioned earlier that we need to know the range of the integers in our input array? We can see why in the code below; the maximum and minimum values often end up being parameters in the counting sort function itself, so if we don’t know these values, we (quite literally) can’t run the algorithm!
// Notice that we needed to know the max/min value in order to use counting sort at all!
function countingSort(array, minimumValue, maximumValue) {
var i;
var z = 0;
var count = [];
// Count the instances of each element.
for (i = minimumValue; i <= maximumValue; i++) {
count[i] = 0;
}
// We now have a placeholder array that we'll use to keep
// track of which element will be sorted into each index.
console.log(count);
// Build up our index count array.
for (i=0; i < array.length; i++) {
count[array[i]]++;
}
console.log(count);
// Modify array and move elements into their sorted location.
for (i = minimumValue; i <= maximumValue; i++) {
while (count[i]-- > 0) {
console.log('item at index ' + z + ' is: ', array[z]);
array[z++] = i;
console.log('moving item ' + i + ' to correct location');
}
}
console.log("Hooray! Array is now sorted!");
return array;
}
Okay, let’s run this code and see what happens. I’ve added some console.log’s to make it a bit more obvious as to what’s actually going on here. We’ll try sorting the exact same array we used in our example: [9, 4, 1, 7, 9, 1, 2, 0]. Notice that we’re passing in 0 as our minimum value and 9 as our maximum value, which is the range of the integers that we’re trying to sort.
var array = [9,4,1,7,9,1,2,0]
countingSort(array, 0, 9)
> (10) [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
> (10) [1, 2, 1, 0, 1, 0, 0, 1, 0, 2]
> item at index 0 is: 9
> moving item 0 to correct location
> item at index 1 is: 4
> moving item 1 to correct location
> item at index 2 is: 1
> moving item 1 to correct location
> item at index 3 is: 7
> moving item 2 to correct location
> item at index 4 is: 9
> moving item 4 to correct location
> item at index 5 is: 1
> moving item 7 to correct location
> item at index 6 is: 2
> moving item 9 to correct location
> item at index 7 is: 0
> moving item 9 to correct location
> Hooray! Array is now sorted!
>> (8) [0, 1, 1, 2, 4, 7, 9, 9]
Interesting! We can see our count array being logged out when it is first initialized, and we can see it after we’ve done the work of tallying. Notice that we do need to create a new array, count, to keep track of our tallying. However, unlike bubble sort or even quick sort, as we append sorted items to our original array, we’re doing the same amount of work each time, and we only need to iterate once over each element. You can see the single-iteration over the array happening in the loop on lines 24–32.
And this is what exemplifies exactly what makes counting sort so efficient.
Even though we need some extra space for the count array, and we have to do some slightly complex operations on that count array, the overall amount of time that this algorithm takes is, for the most part, linear. In other words, the time complexity of this algorithm depends directly on how many elements we have to sort.
This also explains a little bit of why the range and input size of our unsorted array matters so much! The space complexity of counting sort hinges directly upon the range of integers that we have to sort. Remember that we create a count array as a result of this algorithm, and the larger our range (for example, 0–9, or 1–100, or even 0–10,000!), the larger our count array will end up being. This can be pretty terrible if we want to sort just 5 or 10 elements, but we have to create a massive array in order to do that! In such cases, counting sort will be Very Bad Newsâ„¢.
In truth, the space-time complexity of counting sort really amounts to a combination of both the number of elements to be sorted, n, and the range between the largest and smallest element, or k. The true Big O notation of counting sort is O(n + k). However, counting sort is generally only ever used if k isn’t larger than n; in other words, if the range of input values isn’t greater than the number of values to be sorted. In that scenario, the complexity of counting sort is much closer to O(n), making it a linear sorting algorithm.
So how else does counting sort compare to other sorting algorithms we’ve explored so far?
Well, we already know that, when implemented correctly, counting sort runs in close to linear time. Because the algorithm requires a duplicate array (and doesn’t always operate on the original array), it’s classified as an out-of-place algorithm. However, it does manage to maintain the order of the elements as they appeared in the original array, making it a stable sorting algorithm. This ends up being pretty important and useful, and is another advantage of the counting sort algorithm. It also doesn’t require any external memory and can sort small amounts of data in internal memory. Finally, counting sort is unlike other algorithms we’ve looked at in that it is a non-comparison algorithm. And since we’ve learned that it is iterative in its implementation, we know that it is non-recursive.
You might not find yourself using counting sort all that often in practice, but it’s good to know that linear sorting is possible: as long as you know when to use it. Happy counting!
Resources
Even though we might not use counting sort all that frequently, the basics of this particular algorithm come up a lot, especially since it is one of the few algorithms that can run in linear time. It’s helpful to understand how it works in the long run, and if you want to learn more about it, there are some good resources that dive into the mathematics behind the steps we learned about today. Get counting with the links below!
- Counting Sort, Growing With the Web
- Counting Sort, GeeksForGeeks
- Linear Sorting, David S. Babcock
- Sorting in Linear Time (slides), Professor Roger Crawfis
- Counting Sort Visualization, Professor David Galles
- Counting Sort, Department of Computer Science, MIT
- Counting Sort In Minutes, CS Dojo
This post was originally published on medium.com
Top comments (5)
There are also other Θ(n) (linear runtime in best, average and worst case) sorting algorithms. The most popular one may be radix sort.
You sort an array digit by digit by partitioning it into buckets, one bucket for each digit. This step is repeated from least significant to most significant digit, so for k-bit integers, the runtime of the algorithm is Θ(n*k)
As only the partially solved array and buckets for the next iteration need to be stored, the algorithm is more space efficient, requiring only Θ(n) additional space.
An example in base 10 would be:
The array is flattened and we're done:
[18387, 56942, 183352, 296430, 329361, 637850, 663578, 792961, 968160, 990013]Like counting sort it is also stable, out of place and not based on comparisons. It can even be extended to sort floating point numbers and strings.
Edit:
It also sounds awesome
Hi Palle,
I actually just wrote this week's post on radix sort, funnily enough ☺️ You can read it here: medium.com/basecs/getting-to-the-r...
Vaidehi
I really love the way you break down complex concepts into simpler ones with a wild real-world mapping.
However this counting sort is kinda confusing in the sense I've read some resources that say one can apply counting sort only if 'k'(the highest no. in the array) is less than 'n'(the total no. of elements in the array). And even you have mentioned it while explaining its space complexity. However, in your example the highest is 9 and the no. of array elements is 8. Yet we proceeded with counting sort. Is it due to some other governing factor? And why do we have to shift the elements in our count array?
I would love to wrap my head around this concept. Could you please help me out with this?
I had never heard of counting sort before.
It is, perhaps, my favorite sort. But at least 50% of my love for it comes from the cute sheep that I have now mentally associated with counting sort 😛