Data Structures with Generic Types in Java/

...

/

Counting-Based Sorting

Counting-Based Sorting

Learn about counting-based sorting algorithms.

We'll cover the following...

In this section, 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 a as indexes to 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 a 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, …\dots , 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:

int[] countingSort(int[] a, int k) {

  int c[] = new int[k];

  for (int i = 0; i < a.length; i++)

    c[a[i]]++;

  for (int i = 1; i < k; i++)

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

  int b[] = new int[a.length];

  for (int i = a.length - 1; i >= 0; i--)

    b[--c[a[i]]] = a[i];

  return b;

}

Counting-sort analysis

The first for loop in this code sets each counter c[i] such that it counts the number of occurrences of i in a. By using the values of a as indexes, 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. However, this would not work if the elements of a have associated data. Therefore we spend a little extra effort to copy the elements ...