12345678 12345678 A 012345 B

012345 C 012345 CC

2

5

3

0

2

3

0

3

Draw your program execution process in detail.

3

2

2

4

7

7

8

2

0

2

3

0

1

2

2

4

6

7

8

(a) (b) 12345678 12345678

(c) 12345678

B

(f)

Figure 8.2 The operation of COUNTING-SORT on an input array A1::8 , where each element of A is a nonnegative integer no larger than k D 5. (a) The array A and the auxiliary array C after line 5. (b) The array C after line 8. (c)(e) The output array B and the auxiliary array C after one, two, and three iterations of the loop in lines 1012, respectively. Only the lightly shaded elements of array B have been filled in. (f) The final sorted output array B.

COUNTING-SORT.A; B; k/

let C0::k be a new array foriD0tok

Ci D 0 for j D 1 to A:length

CAj D CAj C 1 //Ci nowcontainsthenumberofelementsequaltoi. foriD1tok

Ci D Ci CCi 1 //Ci nowcontainsthenumberofelementslessthanorequaltoi. for j D A: length downto 1

BCAj D Aj CAj D CAj 1

Figure 8.2 illustrates counting sort. After the for loop of lines 23 initializes the array C to all zeros, the for loop of lines 45 inspects each input element. If the value of an input element is i, we increment Ci . Thus, after line 5, Ci holds the number of input elements equal to i for each integer i D 0; 1; : : : ; k. Lines 78 determine for each i D 0; 1; : : : ; k how many input elements are less than or equal to i by keeping a running sum of the array C .