Skip to content

8.2 Counting sort

8.2-1

Using Figure 8.2 as a model, illustrate the operation of $\text{COUNTING-SORT}$ on the array $A = \langle 6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2 \rangle$.

We have that $C = \langle 2, 4, 6, 8, 9, 9, 11 \rangle$. Then, after successive iterations of the loop on lines 10-12, we have

$$ \begin{aligned} B & = \langle, , , , , 2, , , , , \rangle, \\ B & = \langle, , , , , 2, , 3, , , \rangle, \\ B & = \langle, , , 1, , 2, , 3, , , \rangle \end{aligned} $$

and at the end,

$$B = \langle 0, 0, 1, 1, 2, 2, 3, 3, 4, 6, 6 \rangle.$$

8.2-2

Prove that $\text{COUNTING-SORT}$ is stable.

Consider two elements in the input array, $A[s]$ and $A[s + 1]$, such that $A[s] = A[s + 1]$, $1 \le s \le n - 1$.

After the execution of the final fo $r$ loop in $\text{COUNTING-SORT}$, $B[p] = A[s + 1]$ and $B[p - 1] = A[s]$, $2 \le p \le n$. $A[s]$ and $A[s + 1]$ appear in the output array $B$ in the same order as they appear in $A$. Therefore, $\text{COUNTING-SORT}$ is stable.

8.2-3

Suppose that we were to rewrite the for loop header in line 10 of the $\text{COUNTING-SORT}$ as

1
10  for j = 1 to A.length

Show that the algorithm still works properly. Is the modified algorithm stable?

[The following solution also answers Exercise 8.2-2.]

Notice that the correctness argument in the text does not depend on the order in which $A$ is processed. The algorithm is correct no matter what order is used!

But the modified algorithm is not stable. As before, in the final for loop an element equal to one taken from $A$ earlier is placed before the earlier one (i.e., at a lower index position) in the output array $B$. The original algorithm was stable because an element taken from $A$ later started out with a lower index than one taken earlier. But in the modified algorithm, an element taken from $A$ later started out with a higher index than one taken earlier.

In particular, the algorithm still places the elements with value $k$ in positions $C[k - 1] + 1$ through $C[k]$, but in the reverse order of their appearance in $A$.

8.2-4

Describe an algorithm that, given n integers in the range $0$ to $k$, preprocesses its input and then answers any query about how many of the $n$ integers fall into a range $[a..b]$ in $O(1)$ time. Your algorithm should use $\Theta(n + k)$ preprocessing time.

Compute the $C$ array as is done in counting sort. The number of integers in the range $[a..b]$ is $C[b] - C[a - 1]$, where we interpret $C[-1]$ as $0$.