Exercise 8.2.1
Using figure 8.2 as a model, illustrate the operation of
COUNTING-SORTon the array $A = \langle 6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2 \rangle$
This is tricky to do with graphviz, so I'm going to resort to ASCII art.
This is the array we sort
+---+---+---+---+---+---+---+---+---+---+---+
A: | 6 | 0 | 2 | 0 | 1 | 3 | 4 | 6 | 1 | 3 | 2 |
+---+---+---+---+---+---+---+---+---+---+---+
We build an array of counts:
0 1 2 3 4 5 6
+---+---+---+---+---+---+---+
C: | 2 | 2 | 2 | 2 | 1 | 0 | 2 |
+---+---+---+---+---+---+---+
The number of elements before each
0 1 2 3 4 5 6
+---+---+---+---+---+---+----+
C: | 2 | 4 | 6 | 8 | 9 | 9 | 11 |
+---+---+---+---+---+---+----+
Then we start iterating:
1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6
+---+---+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+----+
A: | | | | | | 2 | | | | | | C: | 2 | 4 | 5 | 8 | 9 | 9 | 11 |
+---+---+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+----+
1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6
+---+---+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+----+
A: | | | | | | 2 | | 3 | | | | C: | 2 | 4 | 5 | 7 | 9 | 9 | 11 |
+---+---+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+----+
1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6
+---+---+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+----+
A: | | | | 1 | | 2 | | 3 | | | | C: | 2 | 3 | 5 | 7 | 9 | 9 | 11 |
+---+---+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+----+
1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6
+---+---+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+----+
A: | | | | 1 | | 2 | | 3 | | | 6 | C: | 2 | 3 | 5 | 7 | 9 | 9 | 10 |
+---+---+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+----+
1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6
+---+---+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+----+
A: | | | | 1 | | 2 | | 3 | 4 | | 6 | C: | 2 | 3 | 5 | 7 | 8 | 9 | 10 |
+---+---+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+----+
1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6
+---+---+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+----+
A: | | | | 1 | | 2 | 3 | 3 | 4 | | 6 | C: | 2 | 3 | 5 | 6 | 8 | 9 | 10 |
+---+---+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+----+
1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6
+---+---+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+----+
A: | | | 1 | 1 | | 2 | 3 | 3 | 4 | | 6 | C: | 2 | 2 | 5 | 6 | 8 | 9 | 10 |
+---+---+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+----+
1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6
+---+---+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+----+
A: | | 0 | 1 | 1 | | 2 | 3 | 3 | 4 | | 6 | C: | 1 | 2 | 5 | 6 | 8 | 9 | 10 |
+---+---+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+----+
1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6
+---+---+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+----+
A: | | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | | 6 | C: | 1 | 2 | 4 | 6 | 8 | 9 | 10 |
+---+---+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+----+
1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6
+---+---+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+----+
A: | 0 | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | | 6 | C: | 0 | 2 | 4 | 6 | 8 | 9 | 10 |
+---+---+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+----+
1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6
+---+---+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+
A: | 0 | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 6 | 6 | C: | 0 | 2 | 4 | 6 | 8 | 9 | 9 |
+---+---+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+