[Algo] 8.2 Counting sort

Counting sort 的基本假設
每個 input 都是 0 到 k 的整數

Counting sort 的原理
對每一個 input element $x$，我們要決定的就是有多少 elements 是比 $x$ 小的，一旦決定了之後，我們就知道這個 $x$ 的順位是多少，於是就可以直接塞到它的 position。

Algorithm
@{
\proc{Counting-Sort}(A, B, k)
\li \For i = 0 \;\textbf{to}\; k
\li \;\;\;\;C[i] = 0
\li \For j = 1 \;\textbf{to}\; \textit{length}[A]
\li \;\;\;\;C[A[j]] = C[A[j]] + 1
\li \textup{// C[i] now contains the number of elements equal to i}
\li \For i = 1 \;\textbf{to}\; k
\li \;\;\;\;C[i] = C[i] + C[i - 1]
\li \textup{// C[i] now contains the number of elements less than pr equal to i}
\li \For j = \textit{length}[A] \;\textbf{downto}\; 1
\li \;\;\;\;B[C[A[j]]] = A[j]
\li \;\;\;\;C[A[j]] = C[A[j]] - 1
}@




A[1..n] 是 input array，其中 $A[j] \in \{0, 1, \ldots, k\}$ for $j = 1, 2, \ldots, n$
B[1..n] 是 output array
C[0..k] 是 auxiliary array，提供暫時的變數儲存空間


第 1-2 行：先把 C[1..k] 初始化
第 3-4 行：C[j] 裡面儲存 A[1..n] 裡面有多少 element 是 $j$
第 6-7 行：C[j] 裡面儲存 A[1..n] 裡面有多少 element 是比小於等於 $j$ 的
第 9-11行：對 $j \in \{0, 1,\ldots, k\}$ 而言，因為我們知道有多少 element 是比 $j$ 小的，也就是說我們知道它的大小順序是多少，於是我們直接把它塞到 output array B[1..n] 裡面

Counting sort's running time
The overall running time is $\Theta(n + k)$，which is $\Theta(n)$ if $k = O(n)$.

stable property
stable: keys with same value appear in same order in output as they did in input
因為 counting sort 的第 9-11 行裡面的 index j 是從後面往前數到 1，這樣可以保有 counting sort 的 stable 特性。這個特性在有 satellite data 也跟著 key 一起排序的時候特別重要。