Chapter 8.2

(a)

A:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---+---+---+---+---+---+---+---+---+----+----|
| 6 | 0 | 2 | 0 | 1 | 3 | 4 | 6 | 1 |  3 |  2 |
|---+---+---+---+---+---+---+---+---+----+----|
C:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---+---+---+---+---+---+---|
| 2 | 2 | 2 | 2 | 1 | 0 | 2 |
|---+---+---+---+---+---+---|

(b)

C:
| 0 | 1 | 2 | 3 | 4 | 5 |  6 |
|---+---+---+---+---+---+----|
| 2 | 4 | 6 | 8 | 9 | 9 | 11 |
|---+---+---+---+---+---+----|

(c)

B:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---+---+---+---+---+---+---+---+---+----+----|
|   |   |   |   |   | 2 |   |   |   |    |    |
|---+---+---+---+---+---+---+---+---+----+----|
C:
| 0 | 1 | 2 | 3 | 4 | 5 |  6 |
|---+---+---+---+---+---+----|
| 2 | 4 | 5 | 8 | 9 | 9 | 11 |
|---+---+---+---+---+---+----|

(d)

B:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---+---+---+---+---+---+---+---+---+----+----|
|   |   |   |   |   | 2 |   | 3 |   |    |    |
|---+---+---+---+---+---+---+---+---+----+----|
C:
| 0 | 1 | 2 | 3 | 4 | 5 |  6 |
|---+---+---+---+---+---+----|
| 2 | 4 | 5 | 7 | 9 | 9 | 11 |
|---+---+---+---+---+---+----|

(e)

B:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---+---+---+---+---+---+---+---+---+----+----|
|   |   |   | 1 |   | 2 |   | 3 |   |    |    |
|---+---+---+---+---+---+---+---+---+----+----|
C:
| 0 | 1 | 2 | 3 | 4 | 5 |  6 |
|---+---+---+---+---+---+----|
| 2 | 3 | 5 | 7 | 9 | 9 | 11 |
|---+---+---+---+---+---+----|

(f)

B:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---+---+---+---+---+---+---+---+---+----+----|
| 0 | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 4 |  6 |  6 |
|---+---+---+---+---+---+---+---+---+----+----|

When placing the elements into the output array B, we place the elements with larger indices in A before those with smaller indices, and when we place the elements into B, we are placing them from larger index to smaller index in B too, thus the elements with the same value appear in the output array B in the same order with the input array A.

The algorithm works, but it's not stable, because the elements with the same value appear in the output array in the reverse order.

Count the elements and then accumulate the count \(C\), the range count of \([a..b]\) is \(C[b] - C[a - 1]\).

RANGE-COUNT-PREPROCESS(A)
    let C[0..k] be a new array
    for i = 0 to k
        C[i] = 0
    for j = 1 to A.length
        C[A[j]] = C[A[j]] + 1
    for i = 1 to k
        C[i] = C[i] + C[i - 1]
    return C

RANGE-COUNT(C, x, y)
    if x == 0:
        return C[y]
    return C[y] - C[x - 1]