Course 3 排序 Sort

▓ Outlines 本章重點 Sort分類觀點 初等排序方法 (Avg. Case: O(n2)) Insertion Sort Selection Sort Bubble Sort 高等排序方法 (Avg. Case: O(n log n)) Quick Sort Merge Sort Heap Sort Radix Sort

▓ Sort 分類觀點 Internal Sort v.s. External Sort. Stable Sorting Method v.s. Unstable Sorting Method.

Internal Sort v.s. External Sort 觀點: 資料量的多寡 Internal Sort: Def: 資料量少，可以一次全部置於Memory中進行sort之工作 目前大多數的Sort方法皆屬此類 External Sort: Def: 資料量大，無法一次全置於Memory中，須藉助輔助儲存體 (E.g. Disk)進行sort之工作

Stable Sorting Method v.s. Unstable Sorting Method 假設欲排序的資料中，有多個記錄具有相同的鍵值 (如: …, k, …, k, …)，經過排序之後，結果可能為: …, k, k, …: 會得到此結果的排序方法稱之為Stable …, k, k, …: 會得到此結果的排序方法稱之為Untable 例: 原始: 5, 4, 2, 6, 4, 7, 1 Stable: 1, 2, 4, 4, 5, 6, 7 Unstable: 1, 2, 4, 4, 5, 6, 7 曾有不必要的Swap發生!!

▓ 初等排序方法 Avg. Case Time Complexity: O(n2) Insert Sort Selection Sort Bubble Sort

▓ Insert Sort (插入排序) 將第i筆記錄插入到前面(i-1)筆已排序好的記錄串列中，使之成為i筆已排序好的記錄串列。 (需執行n-1回合) 範例: A sequence 9, 17, 1, 5, 10。以遞增(increase)排序 5: Solution:

根據上例，可知若有n筆記錄，則需做(n-1)回合。 Algorithm主要由2個副程式組成: Insert副程式 將某一筆記錄 x 插入到S[1] ~ S[i-1]等 i-1 筆已排序好的串列中，使之成為 i 筆已排序好的串列。 即: 決定x插入的位置 Sort副程式 (可當作主程式) 將未排序好的記錄透過Insert的動作，使之成為排序好的記錄 共需做n-1回合，且由第二筆資料開始做起，迴圈: for i = 2 to n

Insert副程式 Sort副程式 (可看成主程式)

範例: Insert副程式: 1 2 3 4 5 6 7 8 S 5 7 8 9  j i x   x = S[i]    已排序 未排序  j i 1 2 3 4 5 6 7 8 S 5 7 8 9 x   x = S[i]   

分析 Time Complexity Space Complexity Stable / Unstable Best Case Worst Case Average Case Space Complexity Stable / Unstable

Time-Complexity Best Case: O(n) [分析方法 1]: 當輸入資料已經是由小到大排好時。 Solution: n筆資料需作(n-1)回合，且每回合只比較1次即可決定x的插入位置。總共花費(n-1)次比較即完成Sort工作。 Time complexity = O(n) 比較一次 比較一次 比較一次 比較一次

[分析方法 2]: 利用遞迴時間函數 T(n) = T(n-1) + 1 = (T(n-2) + 1) + 1 = T(n-2) + 2 = … = T(0) + n T(n) = O(n) 前(n-1)筆比較的遞迴執行次數 第 n 筆資料的最佳比較次數 沒有資料，所以比較次數 T(0) = 0

Worst Case: O(n2) [分析方法 1]: 當輸入資料是由大到小排好時。 n筆資料總共比較次數= 1+2+3…+(n-1) = [n(n-1)]/2。 Time complexity = O(n2) Solution: 比一次 比二次 比三次 比四次

= (T(n-2) + (n-2)) + (n-1) = T(n-2) + (n-2) + (n-1) [分析方法 2]: 利用遞迴時間函數 T(n) = T(n-1) + (n-1) = (T(n-2) + (n-2)) + (n-1) = T(n-2) + (n-2) + (n-1) = (T(n-3) + (n-3)) + (n-2) + (n-1) = … = T(0) + 0 + 1 + 2 + … + (n-3) + (n-2) + (n-1) = 1 + 2 + … + (n-3) + (n-2) + (n-1) = n(n-1)/2 T(n) = O(n2) 前(n-1)筆比較的執行次數 第 n 筆資料的最差比較次數 沒有資料，所以比較次數 T(0) = 0

Average Case: O(n2) [分析方法]: 利用遞迴時間函數 T(n) = T(n-1) + n/2 = T(n-1) + cn = T(n-2) + c(n-1) + cn = … = T(0)+ c(1+2+…+n) = c [n(n+1)]/2 ∴T(n) = O(n2) 遞迴呼叫的執行次數 第 n 筆資料的比較次數 第n筆資料與前n-1筆資料可能的比較次數有 1次，2次，3次，…，(n-1)次。因此，第n筆資料與前n-1筆資料的比較次數總合為: 1+2+3+…(n-1) 第n筆資料要比較的資料數為(n-1) 因此，第n筆資料的平均比較次數為:

Space-Complexity Simple 有structure variable，考量參數傳遞是不是call by value: variables 有structure variable，考量參數傳遞是不是call by value: = n, S[ ]若為call by value 傳遞 (根據主程式所傳來的數值型態與數值多寡) = 0 (或一常數，即起始位址值), S[ ]若為call by address 傳遞 (∵主程式只傳陣列的起始位址，無變動空間需求) 在C++中傳遞陣列一般是使用傳址的方式。 ∵在C++中，陣列的名稱是指向陣列的開始位址，所以呼叫函式時，只要將陣列名稱傳給函式即可

 Space Complexity: (1) (或(C), C為一常數) 由以上分析，可以得知: S(P) = C + SP(I) = C + 0 (或一常數) 因此，除了存放輸入資料之外，額外的空間需求(Extra space)是固定的 (e.g., 變數 x, i, j, … 等)。  Space Complexity: (1) (或(C), C為一常數)

Stable / Unstable Stable (穩定的) 說明: Insert副程式: 1 2 3 4 5 6 7 8  S j i 已排序 已排序 未排序 未排序 j i 1 2 3 4 5 6 7 8  S x = S[i] Sort前: 2 3 5 7 8 8   Sort後: 2 3 5 7 8 8   ∵相同鍵值的記錄在排序後， 其相對位置沒有改變，亦即無 不必要的Swap發生, ∴Stable

▓ Selection Sort (選擇排序) 自第i筆到第n筆記錄中，選擇出最小鍵值 (key) 的記錄，然後與第i筆記錄Swap。(需執行n-1回合) 範例: A sequence 9, 17, 1, 5, 10。以遞增(increase)排序 自第 1 筆到第 5 筆記錄中，挑出最小 鍵值的記錄，然後與第1筆記錄Swap 自第 2 筆到第 5 筆記錄中，挑出最小 鍵值的記錄，然後與第2筆記錄Swap 自第 3 筆到第 5 筆記錄中，挑出最小 鍵值的記錄，然後與第3筆記錄Swap 自第 4 筆到第 5 筆記錄中，挑出最小 鍵值的記錄，然後與第4筆記錄Swap

根據上例，可知若有n筆記錄，則需做(n-1)回合。 Algorithm主要由2個副程式組成: Selection副程式 自第 i 筆到第 n 筆記錄中，選擇出最小鍵值 (key) 的記錄，然後與第 i 筆記錄Swap。 即: 找出最小key值的位置，並做Swap Sort副程式 (可當作主程式) 將未排序好的記錄透過Selection的動作，使之成為排序好的記錄 共需做n-1回合，且由第 1 筆資料開始做起，迴圈: for i = 1 to (n-1)

Sort副程式 (可看成主程式) Selection副程式

範例: (Pass 1  Pass 2) Selection副程式: 1 2 3 4 5 9 10 S 17 5 i j  已排序 未排序 i j  1 2 3 4 5 9 10 S 17 5 smallest       

分析 Time Complexity Space Complexity Stable / Unstable Best Case Worst Case Average Case Space Complexity Stable / Unstable

Best / Average / Worst Case: O(n2) Time-Complexity Best / Average / Worst Case: O(n2) 不論輸入資料如何，演算法中的兩個迴圈皆會執行。

總執行次數:  O(n2) 說明: i值 i = 1 i = 2 … i = n-1 j值 j = 2 to n j = 3 to n j = n-1 to n 第二層迴圈內if指令之比較次數 執行n-1次 執行n-2次 執行1次  O(n2)

Space-Complexity Simple variables 有structure variable，考量參數傳遞是不是call by value: = n, S[ ]若為call by value 傳遞 (根據主程式所傳來的數值型態與數值多寡) = 0 (或一常數，即起始位址值), S[ ]若為call by address 傳遞 (∵主程式只傳陣列的起始位址，無變動空間需求) 在C++中傳遞陣列一般是使用傳址的方式。 ∵在C++中，陣列的名稱是指向陣列的開始位址，所以呼叫函式時，只要將陣列名稱傳給函式即可

 Space Complexity: (1) (或(C), C為一常數) 由以上分析，可以得知: S(P) = C + SP(I) = C + 0 (或一常數) 因此，除了存放輸入資料之外，額外的空間需求(Extra space)是固定的(e.g., 變數 i, j, smallest, temp in Swap函數, …等) 。  Space Complexity: (1) (或(C), C為一常數)

Stable / Unstable Unstable (不穩定的) 說明: (1為最小值，8為最大值) Insert副程式: 1 2 3 4 5 6 7 8  S i 第一回合比較後 1 2 3 4 5 6 7 8  ∵相同鍵值的記錄在排序後，其相對位置有改變，亦即有不必要的Swap發生, ∴Unstable

▓ Bubble Sort (氣泡排序) 由左至右，兩兩記錄依序互相比較 (需執行n-1回合) if (前者 > 後者) then Swap(前者, 後者) 若在某回合處理過程中，沒有任何Swap動作發生，則Sort完成，後續回合不用執行。

範例 1: A sequence 26, 5, 77, 19, 2。以遞增(increase)排序 26 5 77 19 2 Pass 1: Solution: 比較 比較 比較 比較 5 26 19 2 77 5 26 77 19 2 5 26 19 77 2 第一回合後，最大的 Bubble在最高位置上 比較 比較 比較 5 19 26 2 77 5 19 2 26 77 第二回合後，次大的 Bubble在次高位置上 比較 比較 5 2 19 26 77 第三回合後，第三大的Bubble在第三高位置上 比較 2 5 19 26 77 第四回合後，第四大的Bubble在第四高位置上

範例 2: A sequence 9, 17, 1, 5, 10。以遞增(increase)排序 9 17 1 5 10 Pass 1: Solution: 比較 比較 比較 比較 9 1 5 10 17 9 1 5 17 10 9 1 17 5 10 第一回合後，最大的 Bubble在最高位置上 比較 比較 比較 1 5 9 10 17 1 9 5 10 17 第二回合後，次大的 Bubble在次高位置上 比較 比較 第三回合後，沒有任何Swap發生。完成

Algorithm主要由2個副程式組成: Bubble副程式 Sort副程式 (可當作主程式) 由左至右，兩兩記錄依序互相比較 if (前者 > 後者) then Swap(前者, 後者) Sort副程式 (可當作主程式) 將未排序好的記錄透過Bubble的動作，使之成為排序好的記錄 共需做 n-1 回合，且由第 1 筆資料開始做起，迴圈: for i = 1 to (n-1) 若在某回合處理過程中，沒有任何Swap動作發生，則Sort完成，後續回合不用執行

Bubble副程式 Sort副程式 (可看成主程式)

範例: Bubble副程式: 1 2 3 … n-2 n-1 n  1 2 3 … n-2 n-1 n  j i = 1 (即 Pass 1): i = 2 (即 Pass 2): Bubble副程式: j  1 2 3 … n-2 n-1 n   j 比較  1 2 3 … n-2 n-1 n   比較  

分析 Time Complexity Space Complexity Stable / Unstable Best Case Worst Case Average Case Space Complexity Stable / Unstable

Time-Complexity Best Case: O(n) [說明]: 當輸入資料已經是由小到大排好時。 ∵只執行Pass 1，且無任何Swap發生，表示Sort完成。因此，總共只有 (n-1) 次比較即完成Sort。 Time = O(n)。

Worst Case: O(n2) [分析方法 1]: 總執行次數:  O(n2) 當輸入資料是由大到小排好時。 i值 i = 1 … i = n-1 j值 j = 1 to n-1 j = 1 to n-2 j = 1 to 1 第二層迴圈內Swap最差執行次數 執行n-1次 執行n-2次 執行1次  O(n2)

= (T(n-2) + (n-2)) + (n-1) = T(n-2) + (n-2) + (n-1) [分析方法 2]: 利用遞迴時間函數 T(n) = T(n-1) + (n-1) = (T(n-2) + (n-2)) + (n-1) = T(n-2) + (n-2) + (n-1) = (T(n-3) + (n-3)) + (n-2) + (n-1) = … = T(0) + 0 + 1 + 2 + … + (n-3) + (n-2) + (n-1) = 1 + 2 + … + (n-3) + (n-2) + (n-1) = n(n-1)/2 T(n) = O(n2) 前(n-1)筆Swap 的最差執行次數 n 筆資料於Pass 1 時的最差Swap次數 沒有資料，所以Swap次數 T(0) = 0

Average Case: O(n2) [分析方法]: 利用遞迴時間函數 T(n) = T(n-1) + (n-1)/2 = T(n-1) + cn = T(n-2) + c(n-1) + cn = … = T(0)+ c(1+2+…+n) = c [n(n+1)]/2 ∴T(n) = O(n2) 前(n-1)筆資料Swap的平均執行次數 n 筆資料於Pass 1的平均Swap次數 n筆資料可能的Swap次數有 1次，2次，3次，…，(n-1)次。因此，n筆資料的Swap次數總合為: 1+2+3+…(n-1) n筆資料要Swap的資料數為n 因此，n筆資料的平均Swap次數為:

Space-Complexity Simple variables 有structure variable，考量參數傳遞是不是call by value: = n, S[ ]若為call by value 傳遞 (根據主程式所傳來的數值型態與數值多寡) = 0 (或一常數，即起始位址值), S[ ]若為call by address 傳遞 (∵主程式只傳陣列的起始位址，無變動空間需求) 在C++中傳遞陣列一般是使用傳址的方式。 ∵在C++中，陣列的名稱是指向陣列的開始位址，所以呼叫函式時，只要將陣列名稱傳給函式即可

 Space Complexity: (1) (或(C), C為一常數) 由以上分析，可以得知: S(P) = C + SP(I) = C + 0 (或一常數) 因此，除了存放輸入資料之外，額外的空間需求(Extra space)是固定的(e.g., 變數 f, temp in Swap函數, …等) 。  Space Complexity: (1) (或(C), C為一常數)

Stable / Unstable Stable (穩定的) 說明: Insert副程式: 1 2 3 4 5 6 7 8  S 1 2 比較 某一回合後 1 2 3 4 5 6 7 8  ∵相同鍵值的記錄在排序後，其相對位置沒有改變，亦即沒有不必要的Swap發生, ∴Stable

▓ 高等排序方法 Avg. Case Time Complexity: O(n log n) Quick Sort Merge Sort Heap Sort

▓ Quick Sort (快速排序) Avg. case 下，排序最快的algo. Def: 觀念: 將大且複雜的問題切成許多獨立的小問題，再加以解決各小問題後，即可求出問題的Solution。 此即 “Divide-and-Conquer” (切割並征服)的解題策略。 觀念: 將第一筆記錄視為Pivot Key (樞紐鍵 (P.K.) ，或稱Control Key)，在Pass 1 (第一回合) 後，可將P.K.置於 “最正確” 的位置上。 Ex: (經過Pass 1)  把P.K.擺在正確的位置 為切割的概念 (∴可使用遞迴) P.K. Ri Rj , Ri.key  P.K. 且 Rj.key  P.K. P.K.

[關鍵點]: 如何決定P.K.之 “最正確” 位置? 設兩個整數變數 i，j i: 找  P.K.者 j: 找  P.K.者 圖示: : 在數字串列中  P.K.的值 : 在數字串列中  P.K.的值 找到兩國的交界 i j  P.K.  P.K. P.K. Swap Swap Swap

範例: 15, 22, 13, 27, 12, 10, 20, 25由小至大排序 Sol: Pass 1: [12 10 13] 15 [27 22 20 25] Pass 2: [10] 12 [13] 15 [27 22 20 25] Pass 3: 10 12 [13] 15 [27 22 20 25] Pass 4: 10 12 13 15 [27 22 20 25] Pass 5: 10 12 13 15 [25 22 20] 27 Pass 6: 10 12 13 15 [20 22] 25 27 Pass 7: 10 12 13 15 20 22 25 27 i j 15 P.K. 13 20 25 22 27 12 10 Swap Swap Swap [Note]: 只有一顆CPU時: 先排左半部 再排右半部 若有多顆CPU，則 左右半部可各交由 不同的CPU執行!

多顆CPU時的運算過程:

Algorithm主要由2個副程式組成: Partition副程式 Sort副程式 (可當作主程式) 將記錄串中的第一筆記錄經過運算後，置於該記錄串中 “最正確” 的位置上。 即: 找出P.K.的最正確位置 Sort副程式 (可當作主程式) 將Partition後、位於P.K.前後未排序好的兩筆記錄串，透過遞迴的方式分別執行Partition副程式，使之成為排序好的記錄

Sort副程式 (可看成主程式) Partition副程式 i n+1 j  n m list k (P.K.)

分析 Time Complexity Space Complexity Stable / Unstable Best Case Worst Case Average Case Space Complexity Stable / Unstable

Time-Complexity Best Case: O(n log n) [說明]: P.K.之最正確位置恰好將資料量均分成二等份 以Multiprocessor來看，2個CPU的工作量相等，工作可同時做完，沒有誰等誰的問題 [說明]: 時間函數: T(n) = cn + T(n/2) + T(n/2) 時間複雜度求法: 遞迴樹 步驟: 將原本問題照遞迴定義展開 計算每一層的Cost 加總每一層的Cost即為所求 數學解法 左半部 右半部 變數 i 與 j 最多花 n 個執行時間找記錄 (即: 決定P.K.最正確位置所花時間)

遞迴樹 Step 1: 展開 Step 2: 計算每一層的Cost n n n 共有log2n層，表示有 log2n個n。 Step 3: total cost = n log2 n  T(n) = O(n log2 n) n

數學解法 時間函數: T(n) = cn + T(n/2) + T(n/2)  T(n) = 2T(n/2) + cn, c為 >0 的常數 2(2T(n/4) + c(n/2)) + cn = 4T(n/4) + 2cn 4(2T(n/8) + c(n/4)) + 2cn = 8T(n/8) + 3cn 8(2T(n/16) + c(n/8)) + 3cn = 16T(n/16) + 4cn = … = nT(n/n) + log2ncn = nT(1) + cn log2n = n + cn log2n  T(n) = O(n log2n) 共有log2n個 計算結果 T(1) = 1

Worst Case: O(n2) [說明]: 或 當輸入資料是由大到小或由小到大排好時 (切割毫無用處) 輸入資料: 小 大 Pass 1 輸入資料: 小 大 Pass 1 P.K. [0筆] P.K. [ n-1筆 ] 輸入資料: 大 小 Pass 1 P.K. [ n-1筆 ] P.K. [0筆]

時間函數: T(n) = cn + T(0) + T(n-1) (c為>0常數, T(0)=0, T(1)=1) [分析]: 利用遞迴時間函數 (數學解法) 時間函數: T(n) = cn + T(0) + T(n-1) (c為>0常數, T(0)=0, T(1)=1) T(n) = T(n-1) + cn = (T(n-2) + c(n-1)) + cn = T(n-2) + c(n-1) + cn = … = T(0) + c (1 + 2 + … + (n-3) + (n-2) + (n-1) + n) = c  n(n+1)/2 T(n) = O(n2) (改善方法在補充 1)

Average Case: O(n log n) [說明]:  , T(0) = 0 S筆 (n-S)筆 P.K.

Space-Complexity O(log n) ~ O(n) [說明]: Best Case: O(log n) 額外的空間需求，來自於遞迴呼叫所需的Stack空間 而Stack空間的大小，取決於遞迴呼叫的深度 Best Case: O(log n) 由Best Case的時間複雜度分析可以得知，遞迴呼叫的深度是 log n，即: 做過 log n 次呼叫後，整體資料量只剩 1 筆，即可停止呼叫 Worst Case: O(n) 由Worst Case的時間複雜度分析可以得知，遞迴呼叫的深度是(n-1)，即: 做過(n-1)次呼叫後，資料量只剩 1 筆，即可停止呼叫

Stable / Unstable Unstable (不穩定的) 說明: 1 2 3 4 5 6 7 8  S 1 2 3 4 5 6 i j 1 2 3 4 5 6 7 8  S P.K. Swap 某一回合後 1 2 3 4 5 6 7 8  ∵相同鍵值的記錄在排序後，其相對位置有改變，亦即有不必要的Swap發生, ∴Unstable

▓ Merge Sort (合併排序) 觀念: 可分為兩種類型: 將兩個已排序過的記錄合併，而得到另一個排序好的記錄。 Recursive (遞迴) Iterative (迴圈, 非遞迴)

Recursive Merge Sort (遞迴合併排序) 將資料量 n 切成 n/2 與 n/2 兩半部，再各自Merge Sort，最後合併兩半部之排序結果即成。 切割資料量 n 的公式為: [ ]: Run, 已排序好的檔案記錄 Run的長度: Run中記錄個數

Stack 第四層切割所有 資訊依序輸入 第三層切割所有 資訊依序輸入 第二層切割所有 資訊依序輸入 第一層切割所有 資訊依序輸入

Merge the two sorted records (Merge副程式) 需要三個整數變數 i, j, k. If S[i] ≤ S[j] then output S[i], i 前進且 k 前進 else output S[j], j 前進且 k 前進 當 i > mid 或 j > high 時則停止，並將剩餘記錄output i j 11 48] 10 77] 8 59 6 15 4 5 2 [19 61 26 [1 9 7 3 1 S low mid mid+1 high k 77] 10 59 8 26 6 15 4 5 2 61 48 19 11 [1 9 7 3 1 U

根據以上討論，Algorithm主要由2個副程式組成: Merge2副程式 將兩個Run的記錄 (即: 兩筆已排序的記錄)，合併成一筆已排序的記錄 U (即: 合併成一個Run) MergeSort2副程式 (可當作主程式) 執行整個記錄串的遞迴切割 以堆疊中的遞迴切割次序，透過Merge2將所有的Run加以合併 Run 1的長度為 m，Run 2的長度為 n，則合併兩個Run的最多比較次數為 m+n-1 次 Ex: [5,26] [1, 77] 比較3次後，會得到 [1, 5, 26, 77]

Merge2副程式 Run 1的長度為 m，Run 2的長度為 n，則合併兩個Run的最多比較次數為 m+n-1 次

MergeSort2副程式

Iterative Merge Sort (非遞迴合併排序) [ ]: Run, 已排序好的檔案記錄 Run的長度: Run中記錄個數 26, 5, 77, 1, 61, 11, 59, 15, 48, 19 [26] [5] [77] [1] [61] [11] [59] [15] [48] [19] [5, 26] [1, 77] [11, 61] [15, 59] [19, 48] [1, 5, 26, 77] [11, 15, 59, 61] [19, 48] [1, 5, 11, 15, 26, 59, 61, 77] [19, 48] [1, 5, 11, 15, 19, 26, 48, 59, 61, 77] Pass 1: Pass 2: Pass 3: Pass 4:

根據以上討論，Algorithm主要由3個副程式組成: Merge1副程式 將兩個Run的記錄 (即: 兩筆已排序的記錄)，合併成一筆已排序的記錄 U (即: 合併成一個Run) 同Recursion的作法， Run 1的長度為 m，Run 2的長度為 n，則合併兩個Run的最多比較次數為 m+n-1 次 MergePass副程式 在每一回合 (Pass) 中，會處理多次的 “合併兩個Run” 之工作 MergeSort副程式 (可當作主程式) 整個非遞迴的合併排序副程式需執行 回合 (Pass) (補充 4)

為何需要執行 回合？ 以執行完一回合後，Run的長度來看: 有n個數字待排序，一開始每一個Run的長度為 1，且有n個Run 為何需要執行 回合？ 以執行完一回合後，Run的長度來看: 有n個數字待排序，一開始每一個Run的長度為 1，且有n個Run 執行完Pass 1後，最長的Run長度為 21 = 2 執行完Pass 2後，最長的Run長度為 22 = 4 執行完Pass 3後，最長的Run長度為 23 = 8 … 執行完Pass i 後，最長的Run長度為 2i = n (停止)  i = log2n 由於 n 不見得為2的倍數，因此取上限整數 (Ceiling) 以求得能真正完整處理n筆資料排序的回合數。 嚴格說應該為2i >= n

分析 Time Complexity Space Complexity Stable / Unstable Best Case Worst Case Average Case Space Complexity Stable / Unstable

Avg. / Worst / Best Case: O(n log n) 以Recursive Merge Sort角度: [說明]: Time-Complexity Avg. / Worst / Best Case: O(n log n) 以Recursive Merge Sort角度: [說明]: 時間函數: T(n) = T(n/2) + T(n/2) + cn 時間複雜度求法: 遞迴樹 步驟: 將原本問題照遞迴定義展開 計算每一層的Cost 加總每一層的Cost即為所求 數學解法 左半部遞迴 右半部遞迴 最後合併左右兩半部所花時間 ∵ 左、右半部排好之後，各只剩一個Run，且兩半部各有n/2的資料量，其最後一次合併時的比較次數 “最多”為 n/2 + n/2 -1 次，即約 n-1 次 (slide 72) 時間的表示可為 cn 次(∵為線性時間))

遞迴樹 Step 1: 展開 Step 2: 計算每一層的Cost n n n 共有log2n層，表示有 log2n個n。 Step 3: total cost = n log2 n  T(n) = O(n log2 n) n

數學解法 時間函數: T(n) = cn + T(n/2) + T(n/2)  T(n) = 2T(n/2) + cn, c為 >0 的常數 2(2T(n/4) + c(n/2)) + cn = 4T(n/4) + 2cn 4(2T(n/8) + c(n/4)) + 2cn = 8T(n/8) + 3cn 8(2T(n/16) + c(n/8)) + 3cn = 16T(n/16) + 4cn = … = nT(n/n) + log2ncn = nT(1) + cn log2n = n + cn log2n  T(n) = O(n log2n) 共有log2n個 計算結果 T(1) = 1

以 Iterative Merge Sort 角度: 排序 n 個資料，需花費 回合，且每一回合需花費 n+m-1 = O(n) 時間做Merge (不論哪一回合，merge的時間都是與資料量呈線性變化)  總共花 O(n log n)

Space-Complexity 不論是遞迴或是非遞迴方式，都需要暫時性的陣列空間，目的是用來暫存每回合Merge後的Run之結果。 n 愈大，Merge所需的暫存空間就愈多，因此額外的空間需求與 n 成正比。  O(n)

Stable / Unstable Stable (穩定的) 說明: i j ∵ 8 ≤ 8， 先output 8，之後再輸出 8 ∵相同鍵值的記錄在排序後，其相對位置沒有改變，亦即沒有不必要的Swap發生, ∴Stable

▓ Heap Sort (堆積排序) Heap (堆積) Heap Sort 種類 相關的操作與分析 Heap的建立方式 Insert Delete Heap的建立方式 Top-Down Bottom-Up (課本所提之Siftdown) Heap Sort

※ Heap (堆積) 可分為Max-Heap和Min-Heap Max-Heap Min-Heap Def: 為Complete Binary Tree，若不為空，則滿足 所有父點的鍵值  子點鍵值 Root具有最大鍵值 Min-Heap 所有父點的鍵值 ≤ 子點鍵值 Root具有最小鍵值

Heap提供下列運作: Insert element Delete Max. (or Min.) element --兩者擇其一 以下講解皆以Max-Heap為例

Heap之Insert x 動作 Step : 將 x 置於Last Node之後 挑戰失敗 無父點 例: Max-Heap如下，試討論執行下列動作後之結果為何? (1) 插入 “80” (2) 插入 “40”

Sol: (1) (2) 26 26 10 20 5 8 15 80  10 20   5 8 15 80 80 26 40 20 10 8 15 80 5  10 () 26  5 8 15 20   40

Insert x 的Time之分析: O(log n) 說明: Insert x後，x的最大移動距離為 “從leaf到root”，即為樹高，又Heap為Complete B.T. ∴當有n個nodes時，樹高為: Insert之Time為O(log n)

Heap之Delete Max 動作 最大鍵值必定位於Root Step : 移走Root的元素 Step : 將Last Node x刪除並置於Root位置 Step : 從Root往下調整成Max-Heap (Max-Heap調整方法: 跟較大的兒子交換) 例: Max-Heap如下，試討論執行 Delete Max. 後之結果為何?

Sol:     (若再做一次Delete Max.) 77 2 49 19 26 5 2 10 49 26 5 19 10 2

Delete Max 的Time之分析: O(log n) 說明: Step 與Step 的動作只花 O(1) (常數時間) Step 花費時間較多，故以此為主 Last Node x的最大移動距離為 “從Root到leaf”，即為樹高，又Heap為Complete B.T. ∴當有n個nodes時，樹高為: Delete x之Time為O(log n)

Heap的建立方式 以演算法的角度來說，分為兩種方式: Top-Down Bottom-Up (即課本所討論之Siftdown)

Top-Down 連續執行 “Insert” 的動作，每一個步驟執行後均維持Max-Heap 例: 給予 26, 5, 77, 1, 61, 11, 59, 15, 48, 19以Top-Down的方式建立Heap。 Sol: 26 5 26 5 26 77 77 5 26 1 (調整) 5 77 26 77 5 26 1 61 77 61 26 1 5 77 61 26 1 5 11 (調整)

77 61 26 1 5 11 59 77 61 59 1 5 11 26 (調整) 77 61 59 1 5 11 26 15 77 61 59 15 5 11 26 1 (調整)

77 61 59 15 5 11 26 1 48 77 61 59 48 5 11 26 1 15 (調整) 77 61 59 48 5 11 26 1 15 19 77 61 59 48 19 11 26 1 15 5 (調整)

Bottom-Up Step: 先將資料建成Complete B.T. 從 “Last Parent” 往 “Root” 方向，逐次調整每棵子樹成為Max-Heap Stpe 之所以將之建成Complete B.T.，是因為真正在寫程式時，可用Array儲存，會較易搜尋子節點及父節點。(Course 0的Slide48) 例: 給予 26, 5, 77, 1, 61, 11, 59, 15, 48, 19以Top-Down的方式建立Heap。 Sol:  26 5 77 1 61 11 59 15 48 19

 26 5 77 1 61 11 59 15 48 19 26 5 77 48 61 11 59 15 1 19 (調整) 26 5 77 48 61 11 59 15 1 19 26 61 77 48 19 11 59 15 1 5 (調整)

同樣資料，用Top-Down及Bottom-up所建立出來的Max-Heap不一定相同。 26 61 77 48 19 11 59 15 1 5 77 61 59 48 19 11 26 15 1 5 (調整) 同樣資料，用Top-Down及Bottom-up所建立出來的Max-Heap不一定相同。 通常Bottom-up的實際執行速度較快!! (但兩者的Time Complexity相同)

Heap操作 Time Complexity Insert x O(log n) Delete Max Search for Max O(1) 建立Heap (n筆資料) O(n) (補充 3)

※ Heap Sort Step: 將資料先以 “Bottom-up” 的方式建立Max-Heap 執行 n-1 回合的 “Delete Max.” 動作 給予 26, 5, 77, 1, 61, 11, 59, 15, 48, 19，寫出Heap Sort的過程 Sol: 先以 “Bottom-up” 的方式建立Max-Heap 77 61 59 48 19 11 26 15 1 5

 執行 n-1 回合的 “Delete Max.” 動作 Pass 1: 77 Pass 2: 77, 61 5 77 61 48 59 15 19 11 26 5 1 61 59 (調整) 48 19 11 26 15 1 5 1 61 59 48 26 15 19 11 1 5 48 59 (調整) 15 19 11 26 5 1

Pass 3: 77, 61, 59 Pass 4: 77, 61, 59, 48 5 59 48 19 26 15 5 11 1 48 26 (調整) 15 19 11 1 5 1 48 26 19 11 15 5 1 (調整) 19 26 15 5 11 1

Pass 5: 77, 61, 59, 48, 26 Pass 6: 77, 61, 59, 48, 26, 19 Pass 7: 77, 61, 59, 48, 26, 19, 15 26 1 19 15 11 1 5 (調整) 19 11 15 5 1 5 19 15 5 11 1 (調整) 15 11 1 5 15 1 (調整) 11 5 1 5 11 1

Pass 8: 77, 61, 59, 48, 26, 19, 15, 11 Pass 9: 77, 61, 59, 48, 26 , 19, 15, 11, 5 Pass 10: 77, 61, 59, 48, 26, 19, 15, 11, 5, 1 1 11 (調整) 5 1 5 1 1 5 (調整) 1 1 1

How to 小大 將Max-Heap Sort的結果push到一個stack，最後再pop。 使用Min-Heap Sort輸出即是。

分析 Time Complexity Space Complexity Stable / Unstable Best Case Worst Case Average Case Space Complexity Stable / Unstable

Time-Complexity Avg. / Worst / Best Case: O(n log n) 以Heap Sort的執行步驟 (Algorithm) 來說明: Step: 將資料先以 “Bottom-up” 的方式建立Max-Heap 執行 n-1 回合的 “Delete Max.” 動作 Step : 建立Max-Heap會花費 O(n) 時間 Step : 需執行 (n-1) 回合的 Delete Max 動作，而每一次的 Delete Max 動作需花費 O(log n) 時間  Step  共花費 O(n log n) ∴ 整個Heap-Sort 花費 O(n) + O(n log n)  O(n log n) 時間

Space-Complexity 主程式有一個Simple variable (一般變數) 與Structure variable (即: Array，存放構成Heap的Complete Binary Tree) 由以上分析，可以得知: S(P) = C + SP(I) = C + 0 (或一常數) 因此，除了存放輸入資料之外，額外的空間需求(Extra space)是固定的。 The algorithm is called an in-place sort (原地置換). --額外的空間需求不會隨著要被排序的資料個數n而增加。  Space Complexity: (1) (或(C), C為一常數)

Stable / Unstable Unstable (不穩定的) 說明: 有一組資料: 8, 8, 77, 其Max-Heap如下。若進行Heap Sort時，執行一回合的Delete Max: 77 8 8 Delete Max (接下來，8會比8早被輸出!!) 77, 8, 8 ∵相同鍵值的記錄在排序後，其相對位置有改變，亦即有不必要的Swap發生, ∴Unstable

皆採用 Comparison & Swap 技巧 即: 利用鍵值 (Key) 來與欲排序的數字做比較，合乎某種條件就將Key與被比較的數字做交換的動作 已有科學家証明，若採用此技巧所開發出來的演算法，(n log n)的時間已是最好的，不會出現有比該時間更有效率的演算法。(補充 2) Time Complexity Best Worst Avg. Space Complexity Stable/Unstable Insert Sort O(n) O(n2) O(1) Stable Select Sort Unstable Bubble Sort Quick Sort O(n log n) O(log n) ~ O(n) Merge Sort Heap Sort

補 充

補 1: 改善Quick Sort在Worst Case下的執行時間 避免挑到最小值或最大值作為Pivot Key 作法: 使用 “middle-of-three” 假設: 步驟: m = [(low+high)/2] 找出 list[low], list[m], list[high]這三筆記錄的中間鍵值 (即: 誰第二大) 將此筆記錄與list[low]交換 Apply “Quick Sort” 可保証第一筆記錄絕對不是最小值或最大值 low m high 1 2 3 4 5 6 7 list

補 2: 排序方法能達到多快? 假設排序方法的設計是採用 “Comparison & Swap” 技巧 利用決策樹 (Decision Tree) 來判斷: Decision Tree: 描述Sort過程中，各種狀況的比較過程 Non-leaf Node: 表示 “Comparison” 左、右分枝: 表示 “Yes” or “No” Leaf: 排序結果 例: 試說明3個資料 a，b，c 排序之Decision Tree. Sol: a ≤ b Yes No b ≤ c Yes No b ≤ c Yes No a ≤ c Yes No a ≤ c Yes No c, b, a a, b, c a, c, b c, a, b b, a, c b, c, a

[說明]: n 個資料做Sort，有 n! 個可能的排序結果。因此，Sort 的 Decision Tree有 n! 個 Leaf nodes。 根據二元樹之三個基本定理的 [定理一]，我們可以知道 2i-1 = n!  i-1 = ， ∴i = +1，表示此Tree的高度至少為 +1 。 比較次數為  又 n!  ，(Course 1) ∴  log = (n/2) log (n/2) ≤ O(n log n) = (n log n)  (n log n)

補 3: 建立Heap花費 O(n) 時間 O(n) 樹高為k (最後的父點) 在第 i 層，最多有2i-1個節點 … Time

補 4: Iterative Merge Sort 的演算法說明 Algorithm主要由3個副程式組成: Merge1副程式 將兩個Run的記錄 (即: 兩筆已排序的記錄)，合併成一筆已排序的記錄 U (即: 合併成一個Run) MergePass副程式 在每一回合 (Pass) 中，會處理多次的 “合併兩個Run” 之工作 MergeSort副程式 (可當作主程式) 整個非遞迴的合併排序副程式需執行 回合 (Pass)

Merge1副程式 Run 1的長度為 m，Run 2的長度為 n，則合併兩個Run的最多比較次數為 m+n-1 次

MergePass副程式

範例 1: MergePass副程式: 1 2 3 4 5 6 7 8 9 10 [5 26] [1 77] [11 61] [15 59] 執行 Pass 2: (n = 10, L = 2) i = 1 時: 做 merge1(S[ ], U[ ], 1, 2, 4) i = 5 時: 做 merge1(S[ ], U[ ], 5, 6, 8) i = 9 時: 做 for 迴圈 MergePass副程式: 1 2 3 4 5 6 7 8 9 10 [5 26] [1 77] [11 61] [15 59] [19 48] 26 15 59

範例 2: MergePass副程式: 1 2 3 4 5 6 7 8 9 10 [1 11 15 26 59 61 77] [19 48] 執行 Pass 4: (n = 10, L = 8) i = 1 時: 做 if條件後的 merge1(S[ ], U[ ], 1, 8, 10) MergePass副程式: 1 2 3 4 5 6 7 8 9 10 [1 11 15 26 59 61 77] [19 48] 19 48

MergeSort副程式 i = 1 i = 2 i = 4 i = 8 執行 ┌log210┐= ┌3.┐= 4個回合(Pass)

補 5: Radix Sort (基數排序) 採取 “Distribution & Merge” 技巧來Sort。 (分配) (合併) 又稱Bin Sort或Bucket Sort 常用於卡片或信件的分類機 可分為兩種: LSD: Least Significant Digit First MSD: Most Significant Digit First ()

LSD Radix Sort 做法: 假設 r 為基底 (Base, 或稱進制)，則準備 r 個 Buckets，其編號為 0 ~ n-1 假設 d 為最大鍵值的位數個數，則須執行 d 回合才能完成 sort 工作 從最低位數到最高位數執行各個回合，每回合做: 依位數值，將資料分配到對應的 Bucket 中 … Distribution 合併 r 個 Buckets (從 0 ~ n-1) … Merge

範例 將下列數字以LSD Radix Sort加以排序 (Base = 10) 179, 208, 306, 93, 859, 984, 55, 9, 271, 33 Sol: Base = 10, ∴準備 10個桶子，編號為 0 ~ 9 最大的數值是984，有三個位數，∴d = 3，同時可知道需執行 3 個回合才會完成 Sort 工作 從最低位數 (個位數) 開始執行各回合: Pass 1: (針對個位數) Bucket: 0 1 2 3 4 5 6 7 8 9 分配: 合併: 271, 93, 33, 984, 55, 306, 208, 179, 859, 9 9 33 859 271 93 984 55 306 208 179

Pass 2: (針對十位數) (以Pass 1 的結果做為Pass 2 的輸入) Bucket: 0 1 2 3 4 5 6 7 8 9 分配: 合併: 306, 208, 9, 33, 55, 859, 271, 179, 984, 93 Pass 2: (針對百位數) (以Pass 2 的結果做為Pass 3 的輸入) 合併: 9, 33, 55, 93, 179, 208, 271, 306, 859, 984 9 208 859 179 306 33 55 271 984 93 93 55 33 271 9 179 208 306 859 984

分析 Time Complexity Space Complexity Stable / Unstable

Time-Complexity 說明: d: 回合數，r: 基底，n: 資料數目 ∵總共須執行 d 回合，而每一回合花費 O(n+r) 時間，其中: 分配 n 個資料的時間: O(n) 合併 r 個 Buckets的時間: O(r) ∴總共花費 O(d(n+r)) 時間

Space-Complexity 說明: ∵準備 r 個 Buckets，而每個 Buckets的Size最多為 n ∴ O(nr)

Stable / Unstable Stable (穩定的) 說明: …, 8, …, 8, … 說明: …, 8, …, 8, … Bucket: 0 1 2 3 4 5 6 7 8 9 分配: 合併: …, 8, 8, … 8 8 ∵相同鍵值的記錄在排序後，其相對位置沒有改變，亦即沒有不必要的Swap發生, ∴Stable

Time Complexity Best Worst Avg. Space Complexity Stable/Unstable Insert Sort O(n) O(n2) O(1) Stable Select Sort Unstable Bubble Sort Quick Sort O(n log n) O(log n) ~ O(n) Merge Sort Heap Sort Radix Sort O(d(n+r)) O(rn)