[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 是線性的。

[Algo] Exercise 8.3

Exercise 8.3-2
Which of the following sorting algorithm are stable: insertion sort, merge sort, heapsort, and quicksort? Give a simple scheme that makes any sorting algorithm stable. How much additional time and space does your scheme entail?
solution:
(1) insertion sort, merge sort are stable.
(2) We store the index value of each element, and compare the index value if there is a tie. Thus, the additional time requirement will not be affected asymptotically due to adding constant work only during comparison. The additional space requirement is that we require $\lg n$ bits to store index value resulting in $O(n\lg n)$ bits additional space.

Exercise 8.3-3
Use induction to prove that radix sort works. Where does your proof need the assumption that the intermediate sort is stable?
solution:
Basis: If $d = 1$, sorting on that digit sorts the array correctly.
Inductive step: Assume that RADIX-SORT sorts $d-1$ digits correctly. Consider two elements $a$ and $b$, with their $d$th digit $a_d$ and $b_d$ respectively.
(1) $a_d > b_d$ and $b_d > a_d$ : RADIX-SORT works correctly, because of most significant bit dominates regardless of the lower $d-1$ digits.
(2) $a_d = b_d$ : RADIX-SORT leaves $a$ and $b$ in the same order because it is stable sort. The order is correct since lower $d-1$ digits sorts correctly. That's why we need that the intermediate sort must be stable.

Exercise 8.3-4
Show how to sort n integers in the range 0 to $n^2 - 1$ in $O(n)$ time.
solution:
Using Lemma 8.4, we know that $k = n^2$, $b = \lceil 2\lg n\rceil$ and we choose $r = \lfloor \lg n\rfloor$, then RADIX-SORT can sort these numbers in $O((2\lg n / \lg n)(n + 2^{\lg n})) = O(2(n + n)) = O(n)$ running time.

Exercise 8.3-5
In the first card-sorting algorithm in this section, exactly how many sorting passes are needed to sort d-digit decimal numbers in the worst cas? How many piles of cards would an operator need to keep track of in the worst case?
solution:
There are $$1 + 10 + 10^2 + \cdots +10^{d-1} = \frac{10^d - 1}{10 - 1} = \frac{10^d - 1}{9}$$ passes needed to sort all numbers.
Each time we recursively sort numbers in a bin, we must keep track of other 9 bins. And we have to recursively sort the numbers for each digit. Hence we have to keep track of $9d$ piles of cards in the worst case.

[Algo] 8.3 Radix sort

Radix sort 的原理

假設 input array 裡的每個 element 都是 d-digit，整個 radix sort 的精神就是從 least significant bit 開始往 most significant bit 排序，在這邊我們用來排序每個 bit 的是用有 stable 性質的 sorting algorithm (counting sort)，經過 d 個 pass 之後，整個演算法就大功告成了，注意不是從 most significant bit 開始喔！

Radix sort algorithm

@{
\proc{Radix-Sort}(A, d)
\li \For i = 1 \;\textbf{to}\; d
\li \;\;\;\;\textup{use a stable sort to sort array}\; A \;\textup{on digit}\; i
}@

Lemma 8.3
Given $n$ $d$-digit numbers in which each digit can take on up to $k$ possible values, RADIX-SORT correctly sorts these numbers in $\Theta(d(n + k))$ time.
proof: 當每個 digit 的值域 k 不要太大，COUNTING-SORT是個不錯的選擇。每個 pass 裡，我們都花 $\Theta(n + k)$ 的時間來排序 $n$ 個 digit。總共有 $d$ 個 passes，所以總共需要 $\Theta(d(n + k))$ 的 running time。$\blacksquare$

當 $d$ 是常數，而 $k = O(n)$，RADIX-SORT 就是 linear time 的 sorting algorithm。

Lemma 8.4
Given $n$ $b$-bit numbers and any positive integer $r \leq b$, RADIX-SORT correctly sorts these numbers in $\Theta((b/r)(n + 2^r))$ time.
proof: 在 RADIX-SORT 裡面，我們每次排序都只針對一個 digit 去做 stable sort，也就是它的值域只有 0 跟 1 而已，其實也可以把 $r$ 個 digit 看成一個 pass 來做 stable sort，變成每個 pass 所作 sorting 的值域變成 $2^r - 1$，這樣我們只要 $\lceil b/r \rceil$ 次 pass 就可以完成了。
於是整個 running time 就是 $\Theta(d(n + k)) = \Theta(\lceil b/r \rceil(n + 2^r - 1)) = \Theta((b/r)(n + 2^r)) \blacksquare$

如何選擇適當的 r
(1) $b < \lfloor \lg n \rfloor$：此時 $n + 2^r = \Theta(n)$，於是令 $r = b$ 時，running time 是 $(b/b)(n + 2^b) = \Theta(n)$，這樣就會是 asymptotically optimal 的了。
(2) $b \geq \lfloor \lg n \rfloor$：此時選擇 $r= \lfloor \lg n \rfloor$，整個 running time 就是 $\Theta((b/\lg n)(n + n)) = \Theta(bn/ \lg n)$

[Algo] Exercise 8.2

Exercise 8.2-2
Prove that COUNTING-SORT is stable.
solution: see solution 8.2-3.

Exercise 8.2-3
Suppose that the for loop header in line 9 of the COUNTING-SORT procedure is rewritten as
9  for j = 1 to length[A]
Show that the algorithm still works properly. Is the modified algorithm stable?
solution:
The modified algorithm is not stable, though it works properly. No matter how j runs from 1 or from length[A], the correctness of the algorithm will not be affected. Because C[0..k] is well established. When index j is running from 1 to length[A], the element which is taken from A earlier is put in B at later index. It violates the stable property.

Exercise 8.2-4
Describe an algorithm that, given $n$ integers in the range 0 to $k$, preprocesses its input and then answers any query about how many of the n integers fall into a range [a..b] in $O(1)$ time. Your algorithm should use $\Theta(n + k)$ preprocessing time.
solution:
We can design an algorithm that is according to the COUNTING-SORT algorithm. Then the answer to the query is determined by $C[b] - C[a-1]$ in $O(1)$ running time. (We set $C[-1] = 0$.)

[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 一起排序的時候特別重要。

[Algo] Exercise 8.1

Exercise 8.1-1
What is the smallest possible depth of a leaf in a decision tree for a comparison sort?
solution:
At least each element in $\langle a_1, a_2, \ldots , a_n\rangle$ has to be compared. Hence the smallest depth is n-1.

Exercise 8.1-2
Obtain asymptotically tight bounds on $\lg(n!)$ without using Stirling's approximation. Instead, evaluate the summation $\sum_{k=1}^n \lg k$ using technique from Section A.2.
solution:
Since  $\langle \lg k \rangle$ is an increasing sequence, we can evaluate the summation by integral
$$\int_{m-1}^n f(x)dx \leq \sum_{k = m}^n f(k) \leq \int_{m}^{n+1}f(x)dx.$$


Exercise 8.1-3
Show that there is no comparison sort whose running time is linear for at least half of the $n!$ inputs of length n. What about a fraction of $1/n$ of the inputs of length n? What about a fraction $1/2^n$?
solution:
Suppose that there exists a comparison sort which sorts $m$ inputs of $n!$ permutations in linear time. Suppose that the height of the portion of the decision tree consisting of $m$ corresponding leaves is $h$. We have $m \leq 2^h$, which gives us $h \geq \lg m$. By Stirling's approximation:
$$n! = \sqrt{2\pi n}(\frac{n}{e})^n(1 + \Theta(\frac{1}{n})),$$
we have

Hence, for $m = n!/2, n!/n, n!/2^n$, $h = \Omega(n\lg n)$. It is impossible for a comparison sort whose running time is linear for $m =n!/2, n!/n, n!/2^n$ of the $n!$ inputs of length n.

Exercise 8.1-4
You are given a sequence of $n$ elements to sort. The input sequence consists of $n/k$ subsequences, each containing $k$ elements. The elements in a given subsequence are all smaller than the elements in the succeeding subsequence and larger than the elements in the preceding subsequence. Thus, all that is needed to sort the whole sequence of length of n is to sort the $k$ elements in each of the $n/k$ subsequences. Show an $\Omega(n \lg k)$ lower bound on the number of comparisons needed to solve this variant of the sorting problem. (Hint: It is not rigorous to simply combine the lower bounds for the individual subsequences.)
solution:
There are only $(k!)^{n/k}$ reachable leaves in such decision tree. Suppose that the height of the decision tree is $h$. We have $2^h \geq (k!)^{n/k}$, which gives us $h \geq (n/k)\lg(k!) \geq (n/k)(k\lg k - k\lg e) = n\lg k - n\lg e = \Omega(n\lg k)$.

[Algo] 8.1 Lower bounds for sorting

Comparison sorts
merge sort, heapsort, ... 以及我們之前所看過的許多 sorting algorithm，都有一個共同的特色：the sorted order they determine is based on comparisons between the input elements。這些 sorting algorithm 因此被稱為 comparison sorts。往下我們將會證明任何的 comparison sort 的 worst case 一定得花費 $\Omega(n \lg n)$ 這麼多的時間。

在這個 section，我們將會假設 input elements 都是相異的，沒有任兩個 elements 是相同的。根據這個假設，我們也假設所有 comparison 的方法都是這樣的形式： $a_i \leq a_j$。這也是唯一可以獲得兩個 elements 他們之間的資訊的唯一 operation。

The decision-tree model
A decision tree is a full binary tree that represents the comparisons between elements that are performed by a particular sorting algorithm operating on an input of a given size.
decision tree model 是所有 comparison sort 的 abstraction。一旦給定了某個 sorting algorithm 以及某個 input 的長度，那這棵 decision tree 也就跟著確定了。

上面那張圖是個 insertion sort 排序 3 個 elements 的 input array 的 decision tree，每個 non-leaf node 以 $i:j$ 表示 $a_i$ 跟 $a_j$ 在做 comparison，其中的 $i:j$ 是指他們的 original position，我們忽略 data movement 的影響。每個 leaf 都會標示 $\langle \pi(1), \pi(2), \ldots , \pi(n) \rangle$，以代表 $a_{\pi(1)} \leq a_{\pi(2)} \leq \ldots \leq a_{\pi(n)}$ 的排序結果。對一個長度為 n 的 array 執行 sorting algorithm 就對應到一條從 root 往下 trace 到某個 leaf 的 path，不同的 input 就對應到不同的 path。

因為長度為 n 的 input array，總共有 $n!$ 種的排列組合，而且每一個排列組合都必須對應到一個 leaf，所以我們知道這棵 decision tree 的 leaves 必須大於 $n !$ 個

A lower bound for the worst case

首先，我們知道任何 height 為 h 的 binary tree 的 leaves 最多就是 $2^h$ 個。然後我們必須瞭解到最長的 path 對應到這個 sorting algorithm 的 worst-case，接下來我們引進一個定理：

Theorem 8.1

Any comparison sort algorithm requires $\Omega(n \lg n)$ comparisons in the worst case.

Proof: 假設有一棵 height 為 h 的 decision tree 有 l 個 reachable leaves，因為我們知道$n!$ 種的排列組合都必須對應到一個 leaf，所以我們可以得到 $n! \leq l$，再來因為任何 height 為 h 的 binary tree 的 leaves 最多就是 $2^h$ 個，所以我們又可以得到 $n! \leq l \leq 2^h$，因此我們知道 $h \geq \lg(n!) = \Omega(n \lg n)$。$\blacksquare$

Corollary 8.2

Heapsort and merge sort are asymptotically optimal comparison sorts.

Proof: 前面我們已經知道 heapsort 以及 merge sort 有 $O(n \lg n)$ 的 upper bound，根據 Theorem 8.1，我們知道他們都有 $\Omega(n \lg n)$ 的 lower bound，故得證。$\blacksquare$