Class Code: AMC621 Instructor: Huilan Chang #w13

Sorting by Distribution (Radix sort)

Radix refers to the base or number system used to represent digits in 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>299>229>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(LSD)      |  | 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所排好的順序。

The pseudocode of radix sort is:

<aside>

RADIX–SORT($A$, $d$)

1. for $i=1$ to $d$

2. use a stable sort to sort array $A$ on digit $i$
   

</aside>

Try to implement RADIX-SORT!

(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. 採用：每個digit是由$r$個bits組成

</aside>

Bucket sort 桶排序法

🔹 An assumption placed on the $n$ input numbers: The input is generated by a random process that distributes elements uniformly over the interval $[0, 1)$.

🔹 設計的想法：

• Bucket sort requires $n$ **buckets (桶子).【so it is not in-place】