Analysis of Sorting Algorithms

Examples Bubble Sort Insertion Sort Quick Sort Merge Sort

氣泡排序(Bubble Sort)(1/7) 所謂排序(sorting)是將輸入資料依照其值的大小以由小而大或由大而小的次序排列的一種程序 氣泡排序法是所有排序法中最著名也是最簡單的一個，又稱為交換(exchange)排序法或下沉(sinking)排序法。

氣泡排序(Bubble Sort)(2/7) 使用氣泡排序法來將陣列中的元素(資料)依照其值以由小而大的次序排列，其做法為將相鄰的兩個資料加以比較，若前一筆(左邊)資料的值大於後一筆(右邊)資料的值，則將此二筆資料互相交換，否則資料的位置即維持不動。 上述的比較及交換過程一直持續進行到最後一筆資料被比對到為止，這稱為一個回合(pass)。第一個回合的比對進行到最後一筆資料為止(n-1次比對)，此時具最大值的資料已經調換至最後(最右邊)的位置了。

第二回合的比對則進行到倒數第二筆資料為止，此時具第二大值的資料已經調換至倒數第二個位置了；…；餘依此類推。 氣泡排序(Bubble Sort)(3/7) 第二回合的比對則進行到倒數第二筆資料為止，此時具第二大值的資料已經調換至倒數第二個位置了；…；餘依此類推。 下頁為氣泡排序演算法:

氣泡排序(Bubble Sort)(4/7)

氣泡排序(Bubble Sort)(5/7) 7 2 8 5 4 2 7 5 4 8 2 5 4 7 8 2 4 5 7 8 2 7 8 5 4 2 7 5 4 8 2 5 4 7 8 2 4 5 7 8 2 7 8 5 4 2 5 7 4 8 2 4 5 7 8 (done) 2 7 5 8 4 2 5 4 7 8 2 7 5 4 8

氣泡排序(Bubble Sort)(6/7) 氣泡排序法的第1回合需要n-1次比較，第2回合需要n-2次比較，…，第n-1回合需要1次比較，因此，其時間複雜度為(for all cases): (n-1)+(n-2)+…+1= ((n-1)+1)*(n-1)/2=n*(n-1)/2=O(n2)

氣泡排序(Bubble Sort)(7/7) 假設有一個陣列具有5個元素8、5、8’、6、7，註標為0~4，其中8與8’二個元素的值都是8，但是為了區別起見，我們將之標示為8與8’。此陣列經由氣泡排序法排序的過程如下。在整個氣泡排序法的過程值中，8與8’的相對位置一直保持不變，也就是8一直排列在8’之前，當一個排序法能夠讓具有相同值的元素維持原來的相對位置時，我們稱這種排序法為穩定(stable)排序法。另外，除了幾個註標變數之外，氣泡排序法不需要額外的記憶體空間來輔助排序的進行，這種不需要額外記憶體空間的排序法稱為就地(in place)演算法。

範例

改良氣泡排序(Improved Bubble Sort) (1/2) 在上列的氣泡排序法執行過程值中，我們觀察到在回合3(Pass 3)執行完畢時，已經沒有任何的元素需要對調了，這是因為所有的元素已經依照順序排列妥當了。若我們能善用上列的事實，在氣泡排序法的每一個回合中均加入是否有任何元素經過對調的檢查，只要一發現某個回合中已經完全沒有元素對調，則馬上可以停止後續的回合的執行，加快排序的速度。

改良氣泡排序(Improved Bubble Sort) (2/2) 改良氣泡排序法在最佳狀況下(此時元素完全依照大小的順序排列)，在執行完回合1(Pass 1)之後，執行了n-1次資料大小比對，發現完全沒有任何的元素對調，此時排序完成。因此，改良氣泡排序法的最佳時間複雜度為O(n)，改良氣泡排序法的最差時間複雜度為O(n2)

範例

範例

插入排序(insertion sort) 從第二個資料開始，每次考慮一資料，並依序插入其前面適當的位置。 Input 45 39 12 25 30 第1回合 第2回合 第3回合 第4回合

插入排序(insertion sort) 基本方法： 類似概念：交考卷時的排序 資料一個接著一個進來 每次有一個資料進入時，找到此資料值的正確位置，插入此數字 當所有資料進入，排序即完成 2018/11/23

Straight insertion sort Algorithm 2.1 Straight Insertion Sort Input: x1,x2,...,xn Output: The sorted sequence of x1,x2,...,xn For j := 2 to n do Begin i := j-1 x := xj While x<xi and i > 0 do xi+1 := xi i := i-1 End xi+1 := x input: 7,5,1,4,3 7,5,1,4,3 5,7,1,4,3 1,5,7,4,3 1,4,5,7,3 1,3,4,5,7

# of data movements M: # of data movements M = (2 + di) xj 1 5 7 4 3 x 1 5 7 4 3   x temporary d4=2  

Analysis of Insertion Sort best case: already sorted di = 0 for 1  i  n M = 2(n  1) = O(n) worst case: reversely sorted d1 = n  1 d2 = n  2 : di = n  i 1 4 7 5 dn = 0 di = (n  i) i=0,n-1di=n(n-1)/2 M = n(n1)/2+2(n  1) = O(n2) average case: xj is being inserted into the sorted sequence x1 x2 ... xj-1 the probability that xj is the largest: 1/j takes 2 data movements the probability that xj is the second largest : 1/j takes 3 data movements : # of movements for xj to be inserted: 2/j+3/j+ ...+(j+1)/j=(j+3)/2 M=j=2,n(j+3)/2= (n+8)(n1)/4 = O(n2)

快速排序法(Quick Sort) 快速排序(Quick Sort)由獲得電腦計算領域最高榮譽Turing Award的C. A. R. Hoare 博士於1962發表，此排序法採用一個稱為Divide-and-Conquer(分割-征服)的遞迴技術，以不斷分割的方式完成排序的動作。 如其名稱所示，此排序法的排序速度相當快，另外，此排序法是一個就地(in place)演算法，也就是說，除了幾個指標變數之外，快速排序不需要額外的記憶體空間來輔助排序的進行。

快速排序法(Quick Sort) 快速排序的作法為選一個元素p當作標準(pivot)，將陣列切割為3部份：快速排序的作法為選一個元素p當作標準(pivot)，將陣列切割為3部份：SP、EP及LP，其中SP包含所有小於p的元素、EP包含所有等於p的元素、LP包含所有大於p的元素。將陣列切割之後，持續以遞迴的方式進行SP部份與LP部份的元素排序，最後再將SP、EP及LP合併即可完成排序。

快速排序法(Quick Sort) 以下為快速排序的演算法，此演算法使用二個指標(「左指標」l與「右指標」r)將陣列中在「左限」及「右限」範圍內的元素切割為3部份。

快速排序法(Quick Sort) 以下為「快速排序」演算法針對陣列的分割實例：

Best case : O(n log n) A list is split into two sublists with almost equal size. log n rounds are needed. In each round, n comparisons (ignoring the element used to split) are required.

Worst case : O(n2) In each round, the number used to split is either the smallest or the largest.

Average case: O(n log n)

合併排序法(merge sort) quick sort的缺點： 採用合併排序法 最差狀況是O(n2) 也就是無法避免切割陣列是否平均 簡化切割原則，每次都切割成一半 以遞迴方式處理 時間複雜度：O(n log n)

範例

Merge Sort The Idea If |A| = 1, the data is already sorted; done. Otherwise: Split the input into two pieces of equal size. Recursively sort these two pieces. Construct a sorted sequence from the two sorted subsequences.

The Merge Procedure Merge(A, p, q, r) ● Copy A[p..q] and A[q + 1..r] to temporary arrays L and R: 1 n1 ← q – p + r 2 n2 ← r – q 3 for i = 1..n1 4 do L[i] ← A[p + i – 1] 5 for j = 1..n2 6 do R[j] ← A[q + j] ● Create two artificial end markers that are never copied to A: 7 L[n1 + 1] ← ∞ 8 R[n2 + 1] ← ∞ ● Repeatedly copy the smallest element from L and R to A: 9 i ← 1 10 j ← 1 11 for k = p..r 12 do if L[i] ≤ R[j] 13 then A[k] ← L[i] 14 i ← i + 1 15 else A[k] ← R[j] 16 j ← j + 1

Merge Sort The Algorithm MergeSort(A, p, r) 1 if p < r 2 then Split the input into 2 pieces of approximately equal size 3 q ← (p + r) / 2 Recursively sort the two halves 4 MergeSort(A, p, q) 5 MergeSort(A, q + 1, r) Merge the two sorted subsequences 6 Merge(A, p, q, r)

Quick Sort Quicksort is a sorting algorithm whose worst-case running time is (n2) on an input array of n numbers. In spite of this slow worst-case running time, quicksort is often the best practical choice for sorting because it is remarkably efficient on the average: its expected running time is O(n long n), and the constant factors hidden in the O(n log n) is quite small.

Q&A