Lecture 6 Quicksort 本章的重點在介紹Quicksort的作法 然後給予時間複雜度的分析。

6.1 Quicksort Quicksort(A[p..r]) Divide: 把 A[p..r] 分成 A[p..q-1] 和 A[q+1..r] A Conquer: 遞迴將 A[p..q-1] 和 A[q+1..r] 排序 Combine: 不需要作任何事 p r x pivot A[p..q-1] q A[q+1..r] x Quicksort也是典型的Divide-and-Conquer： 在分段的時候，我們先選定一個數字x 然後將所有比 x 小的數字都放到左邊，比 x 大的數字都放到右邊 然後左邊右邊分開來處理 Quicksort

2 q  Partition(A, p, r) /* divide */ Quicksort(A, p, r) 1 If p < r then 2 q  Partition(A, p, r) /* divide */ 3 Quicksort(A, p, q-1) /* conquer */ 4 Quicksort(A, q+1, r) /* conquer */ Quicksort

Partition(A, p, r) 1 x  A[r] 2 i  p-1 3 for j p to r-1 4 do if A[j]  x 5 then i  i+1 6 exchange A[i]A[j] 7 exchange A[i+1]A[r] 8 return i+1 Partition就是先前提到的，x 是我們選定的 pivot 比 x 小的數字就放到左邊去 Quicksort

i 和 j 的意義: p i j r x ≤ x > x unrestricted Quicksort i 和 j 都會越來越大 i 的左邊都是小於等於 x 的數字 介於 i, j 中間的數字都是大於 x 在 j 右邊的那些數字則是還沒處理到的 Quicksort

i 和 j 如何改變: p i j r >x x ≤ x > x p i j r x ≤ x > x Quicksort 當 j 那一格的數字比 x 還要大的時候， 我們直接將 j 移到下一格去，這樣仍舊符合我們前一頁定義的 i, j 特性 x ≤ x > x Quicksort

i 和 j 如何改變: p i j r ≤x x ≤ x > x p i j r x ≤ x > x Quicksort 當 j 那格數字小於等於 x 的時候，我們將那個數字跟 i+1 那格的數字交換 然後 i 與 j 各往後移動一格 x ≤ x > x Quicksort

範例: (Partition, x=A[r]=4) p,j p i j r r (a) (f) 2 8 7 1 3 5 6 4 2 1 3 8 7 5 6 4 p,i j p i j r r (b) (g) 2 8 7 1 3 5 6 4 2 1 3 8 7 5 6 4 p,i j p i (c) r r (h) 2 8 7 1 3 5 6 4 2 1 3 8 7 5 6 4 (d) 黃色是pivot x, 灰色的部分是處理過的數字中大於 x 的數字 綠色的部分是處理過的數字中小於等於 x 的數字，白色的則是還沒處理到的數字。 p,i j p i r (i) r 2 8 7 1 3 5 6 4 2 1 3 4 7 5 6 8 p i j r (e) 2 1 7 8 3 5 6 4 Quicksort

6.2 分析 Worst-case: (n2) (對於已排序好的輸入) T(n) = = 猜測: T(n)  c n2 = O(n2) Substituting: T(n)   c  c(n-1)2+(n)  cn2-c(2n-1)+(n)  cn2 (挑選夠大的 c 即可) 因為輸入已經是排序好的 因此我們找到的 x 不能很平均地把數字分段 Quicksort

T(n)=(n2) n n 1 n-1 n n 1 n-2 n-1 1 n-3 n-2 2 3 1 1 2 (n2) Quicksort 由於數字已經排序好，所以每次partition都只會把pivot切開 造成每次partition都很不平均的情況發生 2 3 1 1 2 (n2) Quicksort

Average-case: (n lg n) (假設所有的元素都不相同) T(n)=O(n+X)，X 是 Partition 中第四行的執行次數。 每次呼叫 Partition 的時候，如果 A[i]<x<A[j] 或 A[j]<x<A[i]，A[i] 和 A[j] 將來就不會再互相比較。 Quicksort

範例: 令 A={3，9，2，7，5}。 第一個回合後，A={3，2，5，9，7}。 之後 {3，2} 再也不會和 {9，7} 比較了。 將 A 的元素重新命名為 z1，z2，...，zn，其中 zi 是第 i 小的元素。且定義 Zij={zi，zi+1，...，zj}。 定義zi : zj ：若且唯若第一個從 Zij 選出來的 pivot 是 zi 或 zj。 Quicksort

對於任意的 i 和 j，發生 zi : zj 的機率為 2/(j-i+1)， 因此， X = = < (套用 Harmonic Series) = O(nlg n) Quicksort

n n n lg n n … 1 1 1 1 1 1 1 1 n Total:Θ(n lg n) Quicksort 由於recursion tree的高度為log(n)， 每一層所花的時間為Θ(n) 因此最後的時間是Θ(n log n) … 1 1 1 1 1 1 1 1 n Total:Θ(n lg n) Quicksort

n n n 1 n … ≤n ≤n 1 Total:Θ(n lg n) Quicksort 就算partition的時候沒有像上一頁切得很平均 只要能將一個長度為 n 的數列切成兩份長度比例為 1：9 (甚至 1:1000, 1:10000都可) 的話，時間仍舊是Θ(n log n) ≤n 1 ≤n Total:Θ(n lg n) Quicksort

其他分析 E(n) = = 為了簡單起見，假設 nE(n) = ------(1) (n-1)E(n-1) = ------(2) E(n)為Average Case下的執行時間 q 是 partition 成兩部分的其中一部份長度 (1/n) * { E(q-1) + E(n-q) } for all q = 1 to n 則表示Partition之後平均情況下的執行時間 (用 n-1 替換掉 (1) 裡面的 n) Quicksort

E(n) = (套用 iteration method) = = = = = = (n)+(n) (1)-(2), 可得 nE(n) = E(n) = (套用 iteration method) = = = = = = (n)+(n) = (n)+(n)(lg n)+2 (套用 Harmonic Series) = (nlg n) Quicksort

6.3 Randomized version of quicksort Randomized Algorithm: 使用亂數產生器的演算法。 Pseudorandom-number generator: 一個傳回在統計上看似隨機數字的 deterministic algorithm 。 Randomized-Partition(A, p, r) i  Random(p, r); exchange(A[r], A[i]); return Partition(A, p, r) 之前是選數列中的最後一個數字當作 pivot， 現在是隨便選數列中的任何一個數字當作 pivot，可以有很高的機率可以避免worst case的發生 Quicksort

Exercises Problem 1: 企業喜歡有個好記的電話號碼。用一個好記的詞或片語來拼電話號碼是一個方法。例如，您撥打 TUT-GLOP 就能打到滑鐵盧大學。有的時候號碼中只有一部分的數字被拿來拼字。當您回到您的旅館時，您能撥打 310-GINO 到 Gino’s 點一個披薩。另一個讓電話號碼好記的方法是把數字編組。例如您能撥打”三個十”3-10-10-10 到 Pizza Hut 點您的披薩。 電話號碼的標準格式由七個十進位的數字所構成，其中有一個連字號在三和第四個數字之間(例如：888-1200)。電話的按鍵提供了字母與數字的對應, 如下所示： Quicksort

Exercises A、 B 和 C 對應到 2； D、 E 和 F 對應到 3 G、 H 和 I 對應到 4； J、 K 和 L 對應到 5 M、 N 和 O 對應到 6； P、 R 和 S 對應到 7 T、 U 和 V 對應到 8； W、 X 和 Y 對應到 9 Q 和 Z 沒有對應的數字。連字號不用撥，而且可以視情況增加或刪除。TUT-GLOP 的標準格式是 888-4567，310-GINO 的標準格式是 310-4466，而 3-10-10-10 的是 310-1010。 二個電話號碼如果有同樣標準格式表示他們是相同的。(他們撥同樣的數字。)您的公司正要整理地方企業的電話號碼。為了控制品質，您想要檢查有沒有兩家(或更多)的企業有同樣電話號碼。 Quicksort

Exercises 輸入：第一行包含了一個整數，代表總共有幾筆資料。隨後會接著一個空行。之後的第一行是一個正整數(最大到 100000)，代表要處理的電話號碼的數目。接下來的每一行都有一組電話號碼，由十進位的數字、大寫字母(Q 和 Z 除外)以及連字號所構成。其中剛好有七個字元是字母或數字。每筆資料中間都有一個空行。 輸出：列出所有出現兩次以上的電話號碼。每一行必須是電話號碼的標準格式，接著是該電話號碼出現的次數(兩者用一個空白隔開)。這些電話號碼必須要由小到大排好。如果沒有電話號碼是重複的，那就輸出一行： No duplicate. 在兩筆資料之間要印一個空行。 Quicksort

以下是一個輸出入的實例: Sample Input Sample Output 1 12 4873279 ITS-EASY 888-4567 3-10-10-10 888-GLOP TUT-GLOP 967-11-11 310-GINO F101010 888-1200 -4-8-7-3-2-7-9- 487-3279 310-1010 2 487-3279 4 888-4567 3 Quicksort

Exercises Problem 2: 某家公司正在尋求一個簡單的方法來編寫員工的資訊。目前的做法是各個部門分別列出自己的員工，然後再統一把資料集中送到公司負責人那邊，負責人再將蒐集好的名單根據姓氏排序。但是人力太花時間了，所以負責人希望能有一個程式幫忙做這件事情：輸入所有員工的資料，合併整理之後再輸出。 Quicksort

Exercises 輸入：輸入的第一行包含了公司部門的數目(介於 2 和 12 之間)，接下來會有各個部門的員工資料。每一個部門提供的資料中，第一行是部門的名稱，之後的每一行都有一個員工的資料(直到空行或是檔案結尾為止)。資料格式如下： 稱謂,名字,姓氏,地址,家中電話,辦公電話,校園信箱號碼 (用逗號隔開) 最多只有 20000 個員工。 輸出：以下是輸出的格式：(請參閱輸出實例) -------------------- <稱謂> <名字> <姓氏> <地址> Department: <部門名稱> Home Phone: <家中電話> Work Phone: <辦公電話> Campus Box: <校園信箱號碼> Quicksort

以下是一個輸出入的實例: Sample Input Sample Output Quicksort 2 English Department Dr.,Tom,Davis,Anystreet USA,555-2832,555-2423,823 Mrs.,Jessica,Lembeck,Center Street,555-2543,555-8584,928 Computer Science Mr.,John,Euler,East Pleasure,555-1432,555-2343,126 ---------------------------------------- Dr. Tom Davis Anystreet USA Department: English Department Home Phone: 555-2832 Work Phone: 555-2423 Campus Box: 823 Mr. John Euler East Pleasure Department: Computer Science Home Phone: 555-1432 Work Phone: 555-2343 Campus Box: 126 Mrs. Jessica Lembeck Center Street Home Phone: 555-2543 Work Phone: 555-8584 Campus Box: 928 Quicksort