[Algo] 8.4 Bucket sort

Basic idea
假設我們要排序的是 $[0,1)$ 之間的小數，而且假設這些小數都是 uniformly distributed。Bucket sort 就是把 $[0, 1)$ 分成 n 個長度相同的 intervals，可以看成是 n 個大小一樣的 buckets，然後根據 input 的小數，把他丟到對應的 bucket 裡面，最後每個 bucket 裡面的數字再去做排序，這樣就完成整個演算法了。因為我們假設 input 是 uniformly distributed 的，所以我們期待每個 bucket 裡面的 numbers 都是差不多的。

Algorithm

@{
\proc{Bucket-Sort}(A)
\li n = \textit{length}[A]
\li \For i = 1 \;\textbf{to}\; n
\li \;\;\;\;\textup{insert A[i] into list}\;B[\lfloor nA[i] \rfloor]
\li \For i = 0 \;\textbf{to}\; n - 1
\li \;\;\;\;\textup{sort list}\;B[i]\;\textup{with insertion sort}
\li \textup{concatenate the lists}\;B[0], B[1], \ldots, B[n - 1]\;\textup{together in order}
}@

Running time
整個 running time，可以由 $T(n)$ 來表示，$$T(n) = \Theta(n) + \sum_{i = 0}^{n-1}O({n_i}^2)$$，其中 $n_i$ 是每個 bucket 裡面所佔據的 element 的數量。對左右兩邊取期望值，我們可以得到：$$\mbox{E}[T(n)] = \mbox{E}[\Theta(n) + \sum_{i = 0}^{n - 1}O({n_i}^2)] = \Theta(n) + \sum_{i = 0}^{n - 1}\mbox{E}[O({n_i}^2)] = \Theta(n) + \sum_{i = 0}^{n - 1}O(\mbox{E}[{n_i}^2])$$
接下來我們要將火力集中在如何算 $$\mbox{E}[{n_i}^2]$$ 上面，我們首先定義一個 indicator random variable：$$X_{ij} = \mbox{I}\{A[j]~\mbox{falls in bucket}~i\}$$, for $i = 0, 1, \ldots , n - 1$ and $j = 1, 2, \ldots , n$，因此顯然 $$n_i = \sum_{j = 1}^{n}X_{ij}$$。接下來，我們開始求 $${n_i}^2$$ 的期望值。


其中，$$\mbox{E}[{X_{ij}}^2] = 1 \cdot \frac{1}{n} + 0 \cdot (1 - \frac{1}{n}) = \frac{1}{n}$$
當 $k \neq j$ 的時候，因為我們知道 $X_{ij}$ 跟 $X_{ik}$ 是獨立的，因此 $$ \mbox{E}[X_{ij}X_{ik}] = \mbox{E}[X_{ij}]\mbox{E}[X_{ik}] = \frac{1}{n}\cdot\frac{1}{n} = \frac{1}{n^2}$$
於是，我們可以把 $\mbox{E}[{n_i}^2]$ 的答案拼起來了。
$$\mbox{E}[{n_i}^2] = \sum_{j = 1}^n \frac{1}{n} +\sum_{1 \leq j \leq n}\sum_{1 \leq k \leq n, k\neq j} \frac{1}{n^2} = n \cdot \frac{1}{n} + n(n - 1) \cdot \frac{1}{n^2} = 2 - \frac{1}{n}$$
最後，我們得證

整個 bucket sort 的 expected running time 是線性的。