Sorting Algorithms in Python — Counting Sort

With the last post, I completed the first part about sorting algorithms. In fact, I did all the sorting algorithms based on comparison (not everyone, just the ones I wanted to do).

Those past algorithms were all sorting my making comparisons between the elements of the array. There is, anyway, an alternative to sort arrays without doing so: for this reason, I will show you a couple of sorting algorithms with a linear complexity starting with Counting Sort.

How does Counting Sort work?

For those kinds of sorting algorithms, we start from a liiiitle bit more restrictive hypotheses. In this case, the hypothesis is the following:

• The elements to order are integers in a range from 0 to k.

The approach is quite simple:

1. For every number in the range from 0 to k we count the occurrences in the array to order;
2. For every number in the range from 0 to k, we count the occurrences of values ≤ the considered number.

So we will have two arrays:

1. An array that I will call B, of dimension n (the same dimension of the array to sort), that keeps the sorted values
2. An array that I will call C, of dimension k+1 that keeps the occurrences of every value in the range from 0 to k as stated in point 2 of the previous list.

We just need those two pieces of info to order the array.

Let’s go step-by-step. Suppose we have an array A (with values in the range from 0 to 5) to sort. We create the C array by just counting the occurrences of every number from 0 to 5.

After creating C we have to edit it so that the i-th element of the array keeps track of the number of elements in the starting array that are ≤ than i.

So C becomes this:

Is everything alright? Good.

Starting from the last element of A we access every element; for every element, we use it as the index to access the C array, and finally, we add it to the B array. Confusing, right?

Let’s take the previous image and check the correct insert of the first element. To make everything easier I already ordered the B array:

Let’s proceed step by step:

• The first element of the array is 3;
• I access to the element C[3], it contains the value 7;
• I insert 3 into the element B[7–1]=B[6]
• I decrease the value of C[3]

Let’s do another step:

• I access to the second element of A, it contains the value 5;
• I access to the element C[5], it contains the value 8;
• I insert 5 into the element B[8–1]=B[7]
• I decrease the value of C[5]

So the array C tells us where to insert the value.

Simple as that.

Python Implementation

Here is the Python implementation:

Algorithm Overview

Since this is the third post about sorting algorithms I will not repeat what are the math notations. If you need to refresh your mind you may look at the first post.

Best-case complexity: θ(n+k)

Worst-case complexity: θ(n+k)

Stable: Yep (if there are two elements with the same value their relative order will be kept)

In-place: Nope (there is NOT a maximum number of elements saved outside the starting array)

Conclusions

When we use Counting Sort? Since the execution time is θ(n+k) it is used when k is < than n and we obtain a linear execution time.

As usual, if you want to see the source code you can check my GitHub!