# Exercise 8.2.1

Using figure 8.2 as a model, illustrate the operation of COUNTING-SORT on 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 |
+---+---+---+---+---+---+---+---+---+---+---+      +---+---+---+---+---+---+---+