Software Learning Resource Service Platform CHAPTER 7 搜尋和排序 (Search and Sort) 1

Software Learning Resource Service Platform Search 分類 : Ⅰ. Internal( 內部 ) v.s External search( 外部 ) 內部 : 資料量少，可直接置於記憶體中進行搜尋 外部 : 資料量太大，無法一次置於記憶體，通常 儲存於輔助記憶體中 (Disk 、 Tape) ，再分 批載入進行 search Ⅱ. Static( 靜態 ) v.s Dynamic search( 動態 ) 資料庫中 data 變動程度低、高 2

Software Learning Resource Service Platform Search Ⅲ. Partial key( 部分鍵值 ) v.s whole key search( 整 個鍵值 ) Ⅳ. Actual key v.s Transformation key 之搜尋 Search 可分成四種 : Linear Search Binary Search Fibonacci Search Interpolation Search 3

Software Learning Resource Service Platform Linear Search If list has n records, with list[i].key referring to the key value for record i, then we can search the list by examining the key values list[0].key,…,list[n-1].key, in that order, until the correct record is located, or we have examined all the records in the list. Since we examine the records in sequence, this searching technique is known as a sequential search. 平均比較次數 次 n-2n-1n …… 4

Software Learning Resource Service Platform Binary Search  二元搜尋 (Binary Search) 是找尋一個排序過的檔案，觀念 與二元樹十分類似，需要藉助〝 Random Access 〞機制支 援才可。  This search begins by comparing searchnum and list[middle].key where middle =.There are three possible outcomes: searchnum < list[middle].key:In this case, we discard the records between list[middle] and list[n-1], and continue the search with the records between list[0] and list[middle-1]. 5

Software Learning Resource Service Platform searchnum = list[middle].key: In this case, the search terminates successfully. searchnum > list[middle].key: In this case, we discard the records between list[0] and list[middle] and continue the search with the records between list[middle+1] and list[n-1]. 6 Binary Search

Software Learning Resource Service Platform Procedure BinSearch (f: afile ； var i:integer ； n,k:integer) Var done : boolean ； l,u,m: integer ； Begin l:=1 ； u:=n ； i:=0 ； done:=false ； while ((l<=u) and(not done)) do Begin m:=(l+u) div 2 ； case compare( k, f[m].key) of 〝 > 〞 : l := m+1 {Look in upper half} 〝 = 〞 : Begin i:=m ； done:= true ； End ； 〝 < 〞 : u:=m-1 ； {Look in lower half} end ； {of case} End ； {of while} End ； {of BinSearch} 7 Binary Search

Software Learning Resource Service Platform 12 筆，畫出 Decision tree 8

Software Learning Resource Service Platform Binary Search 二元搜尋法 : 需符合 (1) 檔案中的紀錄必須事先排序過 (2) 檔案是可以 Direct Access file 或 Random file 2.Time Complexity ∵ T(n) = T(n/2)+1 ， T(1) = 1 ∴ T(n) = O( ) 3. 一般而言， n 值小適合 Sequential Search n 值大適合 Binary Search 9

Software Learning Resource Service Platform Fibonacci Search 費式數列 F 0 =0 ， F 1 = 1 ， F i = F i-1 +F i-2,i ≧ 2 0,1,1,2,3,5,8,13,21,34,55,… 公式 : 〝 F a +m = n+1 〞 (1)n: 紀錄個數 (2)F a : 是≦ n+1 之最大費氏數 (3)m: 是≧ 0 之正整數 先求出 F a ，在求出 m (m=(n+1)-F a ) 。 10

Software Learning Resource Service Platform Fibonacci Search (1)n= 33 筆，則 F a = ? m = ? Steps 1. 找≦ n+1= ≦ 34 之最大費氏數 → F 9 Steps 2.m= (n+1)-F a = 34-34=0 n FnFn

Software Learning Resource Service Platform Fibonacci Search 優點 :  只需用到加法與減法而不必用到除法  在平均情況，它的平均搜尋次數少於二分搜尋法 缺點 :  每次必須去求算下一個費氏數  最壞情況，它的平均搜尋次數多於二分搜尋法 12

Software Learning Resource Service Platform Interpolation Search 內插 ( 插補 ) 搜尋的方法是拿 與 相比較，其 中 : f[u].key ， f[l].key 分別是檔案中最大與最小的鍵值 比較 (k, f[l].key) 〝 = 〞 : 找到 〝 < 〞 :u=(l+i)-1 〝 > 〞 :l=(l+i)+1 13

Software Learning Resource Service Platform Interpolation Search 其好壞完全依鍵值的分布而定，在 uniform 分佈時有 最好的效果，在 n>500 時且鍵值為 uniform distribution 時，效果比二元搜尋法還要好 被搜尋的檔案仍需要滿足二個條件 : (1) 檔案中的紀錄必須事先經過排序 (2) 必須是 Direct Access 或 Random access 機制支援 14

Software Learning Resource Service Platform Sorting 定義 : 排序是指將某一群資料按照某一種排列的規則，重新 安排此群資料的次序 (order) 使其形成遞增 ( 或遞減 ) 的 線性次序關係 (Linear Order) 。 對於兩個鍵值 k(i)= k(j) 的紀錄 r(i) 和 r(j) ，如果在原始 檔案中， r(i) 排在 r(j) 之前；而在排序後，檔案中的 r(i) 仍在 r(j) 之前，則稱此排序有穩定性 (stable) 。反之， 如果 r(j) 在 r(i) 之前，則稱此排序為不穩定 (unstable) 15

Software Learning Resource Service Platform Insertion Sort 26 、 5 、 49 、 13 、 6 寫出排序過程 Ans: (1)5 、 26 、 49 、 13 、 6 (2)5 、 26 、 49 、 13 、 6 (3)5 、 13 、 26 、 49 、 6 (4)5 、 6 、 13 、 26 、 49 16

Software Learning Resource Service Platform Algorithm (1)Insert(r, A[ ],i) 副程式 (2)Insort(A[ ],n) 主程式 (1) Procedure Insert(r, A[ ], i)// 將紀錄 r 插入到 A[0]~A[i] 已排序好 之串列中 // Var j : integer ； Begin j:= i ； While r.key<list[j].key Do Begin list[j+1]:=list[j] ； j:= j-1 ； End ； List[j+i]:= r ； End ； 17

Software Learning Resource Service Platform (2) Procedure Insort(Var list : afile ； n:Integer) ； Var j: Integer ； Begin list[0].key:=-∞ ； for j:= 2 to n do insert (list[j], list, j-1) ； End ； 18

Software Learning Resource Service Platform Insertion Sort Ⅰ. Time complexity : worst case 與 average case = O( ) ， best case( 已 照順序排列好者 ) 為 O(n) ，因為只需 n-1 次的比較。 Ⅱ. 插入排序法是穩定的。 e.g ……5… … 排序後 :……5…… … Ⅲ. Space Complexity = O(1) → 僅須固定空間，一為 Dummy Record ，一為 r 變數。 19

Software Learning Resource Service Platform Selection Sort 觀念 : 令在 n 個紀錄裡 R 1, R 2, …, R n ，其鍵值分別為 K 1,K 2,…,K n 欲將這個 n 個紀錄由小到大排列時，則須 執行以下兩個步驟 : ( 一 ) 在所有紀錄中挑選一個具有最小鍵值的記錄然 後將此紀錄與第 i 個位置對調。 ( 二 ) 在剩餘的 n-1 個紀錄中，再次挑選一個具有最小 鍵值的記錄， i 值加 1 ，然後將此紀錄與第 i 個紀錄位 置對調，重複進行步驟 ( 二 ) 直到 i=n 為止。 20

Software Learning Resource Service Platform Procedure SelectSort(R,n) Begin For i:= 1 to n-1 do Begin m := i ； For j = i+1 to n do If k j <k m then m :=j ； End ； {of For loop} If i m then Begin Swap (R i,R m ) ； End ； End ； {of SelectSort} 21 Selection Sort

Software Learning Resource Service Platform Selection Sort Ⅰ. Time complexity: Best 、 Average 、 Worst case 為 O( ) Ⅱ. Space complexity : O(1) Ⅲ. 不穩定排序 (unstable sort) e.g. pass1: pass2: 22

Software Learning Resource Service Platform Bubble Sort 觀念 : Bubble sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. e.g. 26 、 5 、 47 、 19 、 6 寫出排序過程 pass1 :5 、 26 、 19 、 6 、 47 pass2 :5 、 19 、 26 、 6 、 47 pass3 :5 、 6 、 19 、 26 、 47 pass4 :5 、 6 、 19 、 26 、 47 23

Software Learning Resource Service Platform Procedure BubbleSort(R, n) Begin for i=1 to (n-1) do begin f = 0; for j=1 to (n-1) do if R[j+1].key<R[j].key then [swap(R j, R j+1 ); f=1; ] if f=0 then exit // No swap: exit// end; End; {of BubbleSort} 24

Software Learning Resource Service Platform Bubble Sort Ⅰ. Time complexity : Best case : O(n) Worst case : O( ) Average case : O( ) Ⅱ. 為一 stable sort Ⅲ. Space complexity : O(1) 例 : 給予 1 、 2 、 3 、 4 、 5 由小到大排序 → i=1 j 從 1 to n-1 do 比較 (if k j+1 <k j ) 結果無一次成立，故 f 仍為 0 ，所以 exit → 只作 n-1 次比較，但無任何 swap 故為 best case = O(n) 25

Software Learning Resource Service Platform Shell Sort 觀念 :( 版本一 ) 比較第 i 筆與第 [i+span] 筆記錄，若前者 > 後者，則 swap( 前、後 ) ，每回合須持續作到無 swap 發生，才可 停止，以便進入下一回合 ( 回合數依 span 型而定 ) 。 Note: 常見的型有  型 ( 、 )  型  自定型 ( 但最後一回合 span 須為 1) 26

Software Learning Resource Service Platform 26 、 5 、 3 、 8 、 10 、 12 、 1 、 2(span = ) Ans: pass 1: span=[8/2]=4 (1)(2)(3)(4)(5)(6)(7)(8)

Software Learning Resource Service Platform pass 2: span= [4/2]= 2 28 (1)(2)(3)(4)(5)(6)(7)(8) pass 3: 由小到大小寫出即可 span=2/2=1

Software Learning Resource Service Platform ( 版本二 ) 若此回合 span 值 =k ，則表示有 k 條 sublists( 長度約 n/k) 要執行 Insertion sort 給予 30 、 15 、 2 、 8 、 19 、 47 、 3 、 9 、 11 、 6 執行 shell sort (span=5 ， 3 ， 1) Pass 1. Span=5 (1) 跟 (6) ， (2) 跟 (7) ， (3) 跟 (8) ， (4) 跟 (9) ， (5) 跟 (10) 比較則會變成 → 30 、 3 、 2 、 8 、 6 、 47 、 15 、 9 、 11 、 19 (1)(2)(3)(4)(5)(6)(7)(8)(9)(10)

Software Learning Resource Service Platform Pass 2. Span= 3 (1) 跟 (4) 、 (4) 跟 (7) 、 (7) 跟 (10) 比較 (2) 跟 (5) 、 (5) 跟 (8) 比較 (3) 跟 (6) 、 (6) 跟 (9) 比較 得到 8 、 3 、 2 、 15 、 6 、 11 、 19 、 9 、 47 、 30 Pass 3. Span=1 (1)(2)(3)(4)(5)(6)(7)(8)(9)(10)

Software Learning Resource Service Platform Function shell (list,n) { span = n/2 ； while (span ≧ 1) do { repeat f=0 ； / 表有無 SWAP 發生 / for i=1 to n-span do if list[i].key>list[i+span].key then { swap (list[i],list[i+span]) ； f=1 ； } until (f==0) / 此回合持續到無 SWAP 才停止 / span = span/2 ； } 31

Software Learning Resource Service Platform Shell Sort Ⅰ. Time complexity: 到目前為止， Best case 尚未定論，依 span 型 而定 Ⅱ. Space complexity: O(1) Ⅲ. Unstable [ 說明 ] 5 、 、 1 、 8 Pass 1. 1 、 、 5 、 8 → unstable span=2 Worst caseO( ) Avg. caseO( ) Best case O( ) 、 O( ) 、 O( ) 32

Software Learning Resource Service Platform Quick Sort 快速排序，又稱為 partition exchange sort ，就平均時間而 言，快速排序是所有排序中最佳的。 [ 作法 ] 33 Given: (R 0, R 1, R 2, R 3, ……….., R n-3, R n-2 R n-1 ) After first pass: R 1,..…, R S(i)-1, R 0, R S(i), R S(i)+1, …, R S(n-1) Pivot key i j two partitions

Software Learning Resource Service Platform Quick Sort R1R2R3R4R5R6R7R8R9R

Software Learning Resource Service Platform void procedure QuickSort(list, m, n) if (m<n) then i=m, j=n+1, p.k.=list[m].key Repeat repeat i=i+1 until list[i].key ≥p.k. repeat j=j-1 until list[i].key ≤p.k. if (i<j) then swap(list[i], list[j]) Until i ≥ j swap(list[m], list[j]) QuickSort(list, m, j-1) QuickSort(list, j+1, n) End ； {of if} End ； {of Qsort} 35

Software Learning Resource Service Platform Quick Sort Ⅰ. Time complexity: Best case: P.K 正確位置將 data 串列切割成二等分 T(n)= c*n + 2T( ) = 4*T ( )+2cn = n*T ( )+ = n+ cnlogn = O(nlogn) 36

Software Learning Resource Service Platform Quick Sort Worst case: 資料剛好是由小到大或由大到小，所以選到的 key 不是最大就是最小 T(n) ≦ cn + T(n-1) ≦ cn + T( cn + T(n-2)) ≦ 2cn + T(n-2) ≦ 3cn + T(n-3). ≦ (n-1)cn + T(1) = O( ) 37

Software Learning Resource Service Platform Quick Sort Average case 下， Time complexity 為 O(nlogn) Ⅱ. 快速排序是不穩定的排序 (unstable) Ⅲ. Space complexity: O(logn)~O(n) 在額外的需求方面，需要有一些空間當作堆疊來 完成遞迴 的特性，而 stack 的 size 取決於呼叫之深度。 38

Software Learning Resource Service Platform Merge Sort 觀念 : It merges the sorted lists(list[i],…,list[m]) and (list[m+1],…,list[n]), into a single sorted list,(sorted[i],…,sorted[n]). Merge sort 可分為 :  Iterative  Recursive 39

Software Learning Resource Service Platform Iterative 作法 : 原來的檔案視為 n 個已排序且長度為 1 的檔案，把兩兩合併成 個 長度為 2 的檔案 ( 若 n 為奇數，那有一檔案之長度為 1) 。之後， 個 檔案在兩兩合併直到只剩下一個檔案為止。 e.g. 輸入檔案為 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 、 19 、 26 、 48 、 59 、 61 、 77] 40

Software Learning Resource Service Platform Iterative Ⅰ. Time complexity: Best ， Worst ， Average case 為 O(nlogn) Ⅱ. 是 stable 的 sorting method Ⅲ. 需要 O(n) 之額外空間 41

Software Learning Resource Service Platform Recursive  採用〝 Divide and Conquer 〞  作法 : (1)data 串列一律切割成兩等分 (2) 左、右半部子串列各自進行 merge sort (3) 合併左、右半部成一個檔案 42

Software Learning Resource Service Platform 26 、 5 、 77 、 1 、 61 、 11 、 59 、 15 、 48 、 19 [5 、 26] [77] [1 、 61] [11 、 59] [15] [19 、 48] [5 、 26 、 77] [1 、 61] [11 、 15 、 59] [19 、 48] [1 、 5 、 26 、 61 、 77] [11 、 15 、 19 、 48 、 59] [1 、 5 、 11 、 15 、 19 、 26 、 48 、 59 、 61 、 77] 43

Software Learning Resource Service Platform Procedure rMergeSort (Var x:afile ； l, u:Integer ； Var p:Integer ) Begin If l ≧ u Then p:=l else Begin mid := (1+u) div 2 ； rMergeSort(x,l,mid,q) ； / 左半 rMergeSort(x,mid+1,u,r) ； / 右半 ListMerge(x,q,r,p) ； / 合併 q ， r 兩個 run 成一個 run End ； {of if} End ； {of rMergeSort} 44

Software Learning Resource Service Platform Heap Sort 作法 : Heap sort begins by building a heap out of the data set, and then removing the largest item and placing it at the end of the partially sorted array. After removing the largest item, it reconstructs the heap, removes the largest remaining item, and places it in the next open position from the end of the partially sorted array. This is repeated until there are no items left in the heap and the sorted array is full. 45

Software Learning Resource Service Platform 、 21 、 37 、 15 、 52 、 15+ 、 5 、 40 ，則 Heap sort 過程 : Heap Sort

Software Learning Resource Service Platform 輸出 52 輸出 40 47

Software Learning Resource Service Platform 輸出 37 輸出 35 48

Software Learning Resource Service Platform 輸出 21 輸出 15 49

Software Learning Resource Service Platform 輸出 15+ 輸出 5 50

Software Learning Resource Service Platform Heap Sort Ⅰ. Time complexity: Best ， Average ， Worst case 均為 O(nlogn) [ 說明 ] 1. 建立 heap: O(n) → bottom up 法 2. 執行 n-1 回合，每回合花 O(logn) 時間執行〝 Delete Max 〞 動作∴花了 O(nlogn) ，因此總共時間計算 O(n+nlogn)= O(nlogn) Ⅱ. Unstable method Ⅲ. Space complexity: O(1) 51

Software Learning Resource Service Platform Radix Sort  LSD radix sort (1) 假設 r 為使用之基底，需要準備 r 個 buckets (2) 若有 m 位數字 ( 不是 m 個 ) 則 LSD 需要 m 次的過程 52

Software Learning Resource Service Platform 179 、 208 、 306 、 93 、 859 、 984 、 55 、 9 、 271 、 33 作 Radix sort Pass 1. ( 個位數 ) 合併 :271 、 93 、 33 、 984 、 55 、 306 、 208 、 179 、 859 、

Software Learning Resource Service Platform Pass 2. ( 十位數 ) 合併 :306 、 208 、 9 、 33 、 55 、 859 、 271 、 179 、 984 、 93 Pass 3. ( 百位數 ) 合併 :9 、 33 、 55 、 93 、 179 、 208 、 271 、 306 、 859 、

Software Learning Resource Service Platform Radix Sort Ⅰ. Time complexity : d 為最大鍵值位數個數， n=data 數， r = base Ⅱ. Space complexity : → 額外空間需求來自於〝 Bucket size 〞 = r 個 bucket*n Ⅲ. Stable 55

Software Learning Resource Service Platform Summary NameBest timeWorst timeAvg.timespaceStability InsertionO(n)O(1)Y SelectionO(1)N BubbleO(n)O(1)Y ShellO(1)N QuickO(nlogn) O(logn)~O(n)N MergeO(nlogn) O(n)Y HeapO(nlogn) O(1)N 56

Software Learning Resource Service Platform Summary 資料量少且資料已排序過， Insertion sort 是最佳的 在平均情況下 (average case) ， Quick sort 是最佳的 在最壞情況下 (worst case) ， Merge sort 是最佳的， heap sort 是次佳的 57

Software Learning Resource Service Platform Ans: (1) 為一個 complete binary tree ，可分為 min-heap 及 max- heap 以 max-heap 為例，需要滿足 : 1. 所有子點的鍵值均小於父點鍵值 2.Root 為所有 node 中，具有最大鍵值 58 Question:

Software Learning Resource Service Platform (2) 以建 max-heap 為例 :

Software Learning Resource Service Platform

Software Learning Resource Service Platform

Software Learning Resource Service Platform 62 Reference  Ellis Horowitz, Sartaj Sahni, and Susan Anderson-Freed 〝 Fundamentals of Data Structures in C 〞, W. H. Freeman & Co Ltd,  Ellis Horowitz, Sartaj Sahni, and Dinesh Mehta 〝 Fundamentals of Data Structures in C++ 〞 Silicon Pr, 2006  Richard F.Gilberg, Behrouz A. Forouzan, 〝 Data Structures: A Pseudocode Approach with C 〞, S Baker & Taylor Books, 2004  Fred Buckley, and Marty Lewinter 〝 A Friendly Introduction to Graph Theory 〞 Prentice Hall, 2002  〝資料結構 - 使用 C 語言〞蘇維雅譯，松崗， 2004  〝資料結構 - 使用 C 語言〞 蔡明志編著，全華， 2004  〝資料結構 ( 含精選試題 ) 〞洪逸編著，鼎茂， 2005