This post is based on two posts by Geeksforgeeks and interviewcake.
First thing first, what’s counting sort?
Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (a kind of hashing). Then do some arithmetic operations to calculate the position of each object in the output sequence.
Characteristics of counting sort:
- Counting sort makes assumptions about the data, for example, it assumes that values are going to be in the range of 0 to 10 or 10 – 99, etc, Some other assumption counting sort makes is input data will be all real numbers (or some items like inventory stocks that can be represented by real numbers).
- Unlike other algorithms this sorting algorithm is not a comparison-based algorithm, it hashes the value in a temporary count array and uses them for sorting. Because of this characteristic, counting sort runs in $O(n)$ time, making it asymptoticaly faster than comparison-based sorting algorithms like quicksort or mergesort.
- It uses a temporary array making it a non-In Place algorithm.
Weaknesses:
- Restricted inputs. Counting sort only works when the range of potential items in the input is known ahead of time.
- Space cost. As this algorithm will use a counting array to store elements for further sorting, it uses up extra memory space. If the range of potential values is big, then counting sort requires extra double space as that of the original array.
Illustration of Counting Sort:
The algorithm can be divided into two parts, first, we count how many times each item occurs, then we build the sorted output.
Counting Say we have this array, and we know all numbers in the array will be non-negative integers less than or equal to 10:
The idea is to count how many 0’s we see, how many 1’s we see, and so on. Since there are 11 possible values, we’ll use an array with 11 counters (elements), value to which are all initialized to 0.
We’ll iterate through the input once. The first item is a 4, so we’ll add one to counts[4]. The next item is an 8, so we’ll add one to counts[8].
And so on. When we reach the end, we’ll have the total counts for each number:
Building
Now that we know how many times each item appears, we can fill in our sorted array. Looking at counts, we don’t have any 0’s or 1’s, but we’ve got two 2’s. So, those go at the start of our sorted array.
No 3’s, but there are two 4’s that come next.
After that, we have one 6,
one 8,
and three 9’s
And, with that, we’re done!
Below is the implementation of the algorithm:
// to be provided later...
