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.
Suppose positions $i$ and $j$ with $i < j$ both contain some element $k$. We consider lines 10 through 12 of $\text{COUNTING-SORT}$, where we construct the output array. Since $j > i$, the loop will examine $A[j]$ before examining $A[i]$. When it does so, the algorithm correctly places $A[j]$ in position $m = C[k]$ of $B$. Since $C[k]$ is decremented in line 12, and is never again incremented, we are guaranteed that when the for loop examines $A[i]$ we will have $C[k] < m$. Therefore $A[i]$ will be placed in an earlier position of the output array, proving stability.
8.2-3
Suppose that we were to rewrite the for loop header in line 10 of the $\text{COUNTING-SORT}$ as
Show that the algorithm still works properly. Is the modified algorithm stable?
The algorithm still works correctly. The order that elements are taken out of $C$ and put into $B$ doesn't affect the placement of elements with the same key. It will still fill the interval $(C[k − 1], C[k]]$ with elements of key $k$. The question of whether it is stable or not is not well phrased. In order for stability to make sense, we would need to be sorting items which have information other than their key, and the sort as written is just for integers, which don't. We could think of extending this algorithm by placing the elements of $A$ into a collection of elements for each cell in array $C$. Then, if we use a FIFO collection, the modification of line 10 will make it stable, if we use LILO, it will be anti-stable.
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.
The algorithm will begin by preprocessing exactly as $\text{COUNTING-SORT}$ does in lines 1 through 9, so that $C[i]$ contains the number of elements less than or equal to $i$ in the array. When queried about how many integers fall into a range $[a..b]$, simply compute $C[b] − C[a − 1]$. This takes $O(1)$ times and yields the desired output.