Sorting algorithms are one of the foundational algorithm areas in computer science. Here on PythonAlgos, we’ve covered five of the basic sorting algorithms: bubble sort, heap sort, insertion sort, merge sort, and quick sort. These sorting algorithms are all generalizable algorithms. They can be used to sort integers, floats, strings, etc. In this post, we’re going to cover counting sort.
Unlike the five basic sorting algorithms we covered on the resources page, counting sort is not generalizable. What is it and when can we use it? We’ll cover:
- What is Counting Sort (Pseudocode)
- How to Implement Python Counting Sort Algorithm
- Python Counting Sort Function Steps
- Full Code Implementation for Counting Sort Algorithm in Python
- Testing Our Python Counting Sort Algorithm
- When Should I Use Counting Sort?
- Counting Sort Time Complexity
- Prove that Counting Sort is Stable
- Summary of Python Counting Sort Guide and Implementation
What is Counting Sort (Pseudocode)
Counting sort is a sorting algorithm that only works on integers. In its most basic form, counting sort only works on whole numbers (integers greater than or equal to 0). Counting sort can be modified to work with negative numbers too. Let’s look at the steps involved in implementing counting sort.
- Find
n, the maximum integer in the list - Create a list of zeroes of size
n+1where each index corresponds to an integer from0ton - Iterate through the original list, incrementing the index corresponding to the value in the counting list
- Iterate through the counting list and create a cumulative list, where each index contains the correct index that number should be in (ie index
0contains0and index1contains2, that means1goes in the0th and1st indices)
How to Implement Python Counting Sort Algorithm
Let’s take a look at how to implement a Python Counting Sort Algorithm. In this section, we’re going to create a function that will implement the counting sort algorithm on an unsorted list. Our counting sort function will only take one parameter. The unsorted list we need to sort.
The first thing we do in our function is get the size of the unsorted list. Next, we initialize a list of the same size consisting of 0s. We use this list to store the sorted list. Third, we get the max value in the unsorted list. This corresponds to n in the counting sort pseudocode above.
def counting_sort(unsorted: list):
size = len(unsorted)
sorted_list = [0]*size
_max = max(unsorted)Python Counting Sort Function Steps
Luckily for us, the three steps involved in counting sort are pretty straight forward. First, we’re going to get the counts of each integer in the unsorted list. We do this by creating an empty list of 0s of whatever the max number is plus 1 (to include the 0 index). Then, we loop through each entry and increment the index in the count list by one for each time the number appears in our unsorted list.
Second, we want to get the accumulated counts. We do this by looping through each index from one to the max value. For each of these values, we add the value of the last index in the list to the value of the current index in the counting sort count list we created above.The last step is to create the sorted list.
We start with an index that is one less than the size (to account for the 0 index). While this index, i, is greater than or equal to 0, we fill in the sorted list. We use the value of the unsorted list’s i index as the index for the accumulated count and subtract 1 from that to get the index of the sorted list to fill in. Then, we decrement the accumulated list’s value at the index equal to the value of the i index in the unsorted list and the value of i.
Finally, we return the sorted list.
# get counts of each integer in unsorted
count = [0]*(_max+1)
for i in range(size):
count[unsorted[i]] += 1
# get cumulative count
for i in range(1, _max+1):
count[i] += count[i-1]
# create sorted list
i = size - 1
while i >= 0:
sorted_list[count[unsorted[i]] - 1] = unsorted[i]
count[unsorted[i]] -= 1
i -= 1
return sorted_listFull Code Implementation for Counting Sort Algorithm in Python
The above section including the steps of counting sort are part of the function we defined in the section above that. Here is the full code for a Python Counting Sort implementation:
def counting_sort(unsorted: list):
size = len(unsorted)
sorted_list = [0]*size
_max = max(unsorted)
# get counts of each integer in unsorted
count = [0]*(_max+1)
for i in range(size):
count[unsorted[i]] += 1
# get cumulative count
for i in range(1, _max+1):
count[i] += count[i-1]
# create sorted list
i = size - 1
while i >= 0:
sorted_list[count[unsorted[i]] - 1] = unsorted[i]
count[unsorted[i]] -= 1
i -= 1
return sorted_listTesting Our Counting Sort Python Implementation
Now that we’ve written a function to implement counting sort in Python, let’s see how our counting sort function works. Below, I’ve provided three different unsorted lists. Then, we call counting sort on all three of these lists.
unsorted1 = [5, 2, 1, 7, 3, 3, 5, 2, 7, 4, 11]
unsorted2 = [4, 1, 2, 2, 3, 9, 8, 9, 2]
unsorted3 = [6, 1, 1, 8, 3, 2, 4, 4, 2, 1]
print(counting_sort(unsorted1))
print(counting_sort(unsorted2))
print(counting_sort(unsorted3))The sorted lists should look like the sorted lists in the image below.
When Should I Use Counting Sort?
Unlike the basic sorting algorithms we’ve covered on this page, counting sort is not applicable in all circumstances. Counting sort should only be used when you have to sort a list of integers. It is almost always explicitly stated or implicitly implied that counting sort is meant for positive integers.
However, we can actually extend it to also work when we have negative integers. How could we do that? By making a counting list of size m where m is the difference between the max and min number in the list. Perhaps we’ll cover a Python implementation of counting sort with negative numbers in the future.
Counting Sort Time Complexity
What’s the time complexity of counting sort? How long it takes for an algorithm to sort a list is an important factor in picking your sorting algorithm. Counting sort has a time complexity of O(n + m) where n is the size of the list and m is the max number. In other words, the time that it takes to sort your list with counting sort goes up at the same rate as the size of your list.
How is counting sort able to have a linear time complexity while every other sorting algorithm we’ve covered so far is O(n log n) at best? Counting sort buys its time efficiency by requiring extra memory and being limited in its scope. As you can see from counting sort Python implementation, we need two extra lists. These lists are usually different sizes. One corresponds to the number of entries in the list, and the other corresponds to the largest entry.
As we said above, counting sort only works on integers. If the largest entry in our list is much larger than the size of our list, counting sort becomes less efficient. This only becomes a problem when working with large numbers.
Prove that Counting Sort is Stable
Another thing to consider when evaluating sorting algorithms is stability. Counting sort is stable. In this section, we’ll prove that counting sort is stable. It breaks ties between equal numbers by making sure the number that appears first in the unsorted array also appears first in the sorted array.
We’re going to do one better here. We’re going to change the code slightly to prove that counting sort is stable via demonstration. We can use a priority queue and apply counting sort to that to prove that counting sort is stable.
We only have to make a few changes to the code to make our counting sort Python implementation work on priority queues. I’ve commented next to the line in the code below. The main differences are using a lambda function to get the max value and using the [0] suffix whenever we work with the unsorted list to grab the number.
def counting_sort(unsorted: list):
size = len(unsorted)
sorted_list = [0]*size
_max = max(unsorted, key=lambda item:item[0])[0] # change here
# get counts of each integer in unsorted
count = [0]*(_max+1)
for i in range(size):
count[unsorted[i][0]] += 1 # change here
# get cumulative count
for i in range(1, _max+1):
count[i] += count[i-1]
# create sorted list
i = size - 1
while i >= 0:
sorted_list[count[unsorted[i][0]] - 1] = unsorted[i] # change here
count[unsorted[i][0]] -= 1 # change here
i -= 1
return sorted_list
unsorted = [(3,'a'), (1,'a'), (1,'b'), (2,'a'), (2,'b')]
print(counting_sort(unsorted))When we call our counting sort Python implementation on the above priority queue, we get the output shown below.
Summary of Python Counting Sort Guide and Implementation
In this guide we covered how to do a counting sort Python implementation. Counting sort is only implemented when we have data of integers. More traditionally, positive integers. We covered how counting sort is implemented via pseudocode.
Counting sort makes use of an extra two lists and iterates through each of them once. It literally counts the number of times each value appears, hence the name counting sort. We also covered that counting sort has linear time complexity. It scales directly with the max size and the size of the list.
We also adjusted the code to prove that counting sort is stable. We made it so that our counting sort Python implementation worked for priority queues. Then, we sort a priority queue with the adjustment and show that the entries are placed in order. Counting sort always puts numbers in the sorted list in the same order they appear in the unsorted list.
Further Reading
- Python Speech Recognition with the SpeechRecognition Library
- List Directories, Subdirectories, and Files with Python
- A Software Engineer’s Guide to the Orchestration Pattern
- The Best Way to do Named Entity Recognition (NER)
- What is Lemmatization and How to do it in Python
I run this site to help you and others like you find cool projects and practice software skills. If this is helpful for you and you enjoy your ad free site, please help fund this site by donating below! If you can’t donate right now, please think of us next time.
