Counting-Based Sorting
Learn about counting-based sorting algorithms.
In this lesson, we study two sorting algorithms that are not comparison based. Specialized for sorting small integers, these algorithms elude the lower bounds of Theorem 1 in the previous lesson by using (parts of) the elements in as indexes into an array. Consider a statement of the form
This statement executes in constant time, but has c.length
possible different outcomes, depending on the value of a[i]
. This means that the execution of an algorithm that makes such a statement cannot be modeled as a binary tree. Ultimately, this is the reason that the algorithms in this section are able to sort faster than comparison-based algorithms.
Counting-sort
Suppose we have an input array a
consisting of integers, each in the
range . The counting-sort algorithm sorts using an auxiliary
array c
of counters. It outputs a sorted version of a
as an auxiliary array b
.
The idea behind counting-sort is simple: for each , count the number of occurrences of i
in a and store this in c[i]
. Now, after sorting, the output will look like c[0]
occurrences of 0
, followed by
c[1]
occurrences of 1
, followed by c[2]
occurrences of followed by c[k − 1]
occurrences of k − 1
.
Visual demonstration of counting-sort
The code that does this is very slick, and its execution is illustrated below:
The implementation of the countingSort()
method is:
countingSort(array<int> &a, int k) {array<int> c(k, 0);for (int i = 0; i < a.length; i++)c[a[i]]++;for (int i = 1; i < k; i++)c[i] += c[i-1];array<int> b(a.length);for (int i = a.length-1; i >= 0; i--)b[--c[a[i]]] = a[i];a = b;
Counting-sort analysis
The first for
loop in this code sets each counter c[i]
so that it counts
the number of occurrences of i
in a
. By using the values of a
as indices, these counters can all be computed in time with a single for loop. At
this point, we could use c
to fill in the output array b
directly. ...