Data Structures with Generic Types in C++/

...

/

Counting-Based Sorting

Counting-Based Sorting

Learn about counting-based sorting algorithms.

We'll cover the following...

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

c[a[i]]=1c[a[i]] = 1

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 nn integers, each in the range 0,...,k−10,...,k − 1. The counting-sort algorithm sorts aa 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 i∈{0,...,k−1}i \in \{0,...,k − 1\}, 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 2,...,2,. . . , 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 operation of counting-sort on an array of length n = 20 that stores integers 0,...,k − 1 = 9
The operation of counting-sort on an array of length n = 20 that stores integers 0,...,k − 1 = 9

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 O(n)O(n) time with a single for loop. At this point, we could use c to fill in the output array b directly. ...