Data Structures with Generic Types in Python/

...

/

Counting-Based Sorting

Counting-Based Sorting

Learn about counting-based sorting algorithms.

We'll cover the following...

In this lesson we’ll learn about two sorting algorithms that are not comparison-based. Specialized for sorting small integers, these algorithms elude the lower-bounds of Theorem 1 in previous lesson by using (parts of) the elements in a as indices 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 aa 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.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:

Press + to interact
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 counting_sort() is:

Press + to interact
def counting_sort(a, k):

    c = new_zero_array(k)

    for i in range(len(a)):

        c[a[i]] += 1 

    for i in range(1, k):

        c[i] += c[i-1]  

    b = new_array(len(a))

    for i in range(len(a)-1, -1, -1):

        c[a[i]] -= 1        

        b[c[a[i]]] = a[i]   

    return 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 ...