Course: 113-1 Introduction to Algorithms. Lecturer: Huilan Chang. 2024.11.08

Sorting by Distribution (Radix sort)

• An assumption placed on the input numbers: Each element has $d$ digits, each digit has $k$ **possible values, and digit $1$(在最右) is the least significant digit(最不重要). e.g. 328>229>299>199
• Terminology:     The most significant digit (MSD); The least significant digit (LSD) Radix sort 從LSD往MSD做sorting.
• 以下是radix sort演算法的三部曲. (1) Design Assume that the data are in array $A[1..n]$. The idea of radix sort is: 由 LSD 做到 MSD, 每次只依照 “正在考慮的那個digit” 排序.

例如: $d = 3, k = 10$, and each digit is between $0$ to $9$ (inclusive).

| data |  | digit 1      |  | digit 2   |  | digit 3 |
| --- | --- | --- | --- | --- | --- | --- |
| 329 |  | 720 |  | 720 |  | 329 |
| 457 |  | 355 |  | 329   |  | 355 |
| 657  |  | 436 |  | 436     |  | 436 |
| 839 | → | 457 | → | 839 | → | 457 |
| 436 |  | 657  |  | 355 |  | 657 |
| 720 |  | 329 |  | 457 |  | 720 |
| 355 |  | 839 |  | 657 |  | 839 |

注意：都採用stable sorting。作用為何？例如：用digit 1和digit 2排好後，329排在355之前，再用digit 3排時，採用stable sorting，維持329排在355之前。用stable sorting才不會打破之前digits所排好的順序。

<aside>
⭐

The pseudocode of radix sort is:
RADIX–SORT($A$, $d$)

1. **for** $i ← 1$ **to** $d$ **do**
2.     use a stable sort to sort array $A$ on digit $i$.
</aside>

(2) The correctness of radix sort follows by induction on the column being sorted. (skip)

(3) Analysis
Suppose we use counting sort in step 2. Then there are $d$  passes in RADIX-SORT algorithm and each pass takes $\\Theta(n + k)$ time.  Thus RADIX–SORT takes $\\Theta(d(n + k))$ time.

Note. When $d$ is a constant and $k = O(n)$, RADIX–SORT takes linear time.

• We have some flexibility in how to break each key into digits: Take a 32-bit word computer (32位元電腦) as an example. A 32-bit word can be viewed as four 8-bit digits (每個digit是由8個bits組成，共4個digits), where each digit is between 0 to 255 (= $2^8 -1$).  So each digit has 256 = $2^8$ possible values. Thus RADIX–SORT takes $θ((32/8)(n + 2^8))$ time to sort $n$ 32-bit words ($n$個32-bit的數).

<aside> ⭐

Lemma. Given $n$ $b$-bit numbers and any positive integer $r ≤ b$, RADIX-SORT correctly sorts these numbers in $\Theta((b/r)(n + 2^r))$ time. Note. 每個digit是由$r$個bits組成

</aside>

Bucket sort 桶子排序法

• An assumption placed on the $n$ input numbers:

  <aside> ⭐

  The input is generated by a random process that distributes elements uniformly over the interval $[0, 1)$.

  </aside>

• 設計的想法：

  • Bucket sort requires $n$ **buckets (桶子).【so it is not in-place】
  • Since the data are distributed uniformly, each bucket（桶子） contains a constant number of data. 例如: 10 buckets $B[0], B[1], …, B[9]$ ，當中$B[i]$ contains numbers in $[\frac{i}{10} , \frac{i+1}{10} )$. *用閉開區是為配合keys落在 [0, 1)裡。 $B[0]$ contains numbers in $[0,0.1)$ $B[1]$ contains numbers in $[0.1,0.2)$ … $B[9]$ contains numbers in $[0.9,1)$
  • In general, if we have $n$ buckets $B[0], B[1], …, B[n – 1],$ then $B[i]$ contains $[\frac{i}{n} , \frac{i+1}{n} )$. If $x\in [0,1)$, then $x$ is put into $B[\lfloor nx \rfloor]$.

• 以下是bucket sort演算法的三部曲. (1) Design

  <aside> ⭐

  Assume that the data are in array $A[1..n]$. The idea of bucket sort is:

  1. Create buckets $B[0], B[1], …, B[n – 1]$. // In the implementation, each bucket is a linked list.
  2. For each element $A[i]$ in $A$, insert $A[i]$ into bucket $B[\lfloor nA[i] \rfloor]$.
  3. Insertion sort each $B[i]$ and concatenate (連接) $B[0], B[1], …, B[n – 1]$ in order.

  

  </aside>

  例如: $n=10$

  

  <aside>

  Implement: https://colab.research.google.com/drive/14-9-053c6xuiRTFFYOwzj50KQNEiabrR?usp=sharing

  </aside>

  (2) Proof of correctness (skip)

  (3) Analysis

  <aside> ⭐

  The average-case running time of Bucket Sort is $\Theta(n)$.

  </aside>

  Proof. Let $n_i$ be the number of elements in bucket $B[i]$. Since insertion sort runs in quadratic time, the running time of bucket sort is

We now analyze the average-case running time of bucket sort, by computing the expected value of the running time, where we take the expectation over the input distribution. Taking expectations of both sides and using linearity of expectation, we have

It is no surprise that each bucket $i$ has the same value of $E [n_i^2]$, since each value in the input array $A$ is equally likely to fall in any bucket. Define indicator random variables $X_{ij}=I\{A[j] \text{ falls in bucket } i\}$ for $i=0,1,\ldots, n-1$ and $j=1,2,\ldots, n$. (接續板書)

<aside>

</aside>