快速排序法 (Quick Sort).

Presentation on theme: "快速排序法 (Quick Sort)."— Presentation transcript:

1 快速排序法 (Quick Sort)

2 定義 由C. A. R. Hoare 所創的快速排序法。 其主要的原理是利用遞迴概念，將陣列分成二部份：
第一部分中的所有元素的值都小於某一個預先選定的基準值(pivot)， 第二部分中的所有元素的值都大於基準值； 這二部分的資料再根據同樣的方式，再分別作快速排序。

3 基本運算 假設要排序的元素如下： K(1),K(2),……,K(n) 則快速排序法的一個步驟是將串列分割成兩個子串列

4 其演算的步驟： 若n=1，則return； 令分隔點K(p)為第一筆資料的值 由左向右找出一筆資料K(i)，使得K(i)＞K(p)；
由右向左找出一筆資料K(j)，使得K(j)＜K(p)； 若i＜j則K(i)與K(j)交換，並回到步驟２； 若i≧j，則將K(j)與K(p)交換，並以j為基點將資料分割成左右兩半，然後分別針對左右兩半進行步驟１～５。

5 演算法 ＝＞C語言程式碼 quick_sort(int a[ ], int l, int r) { int p, i, j, t ;
if ( l < r) i = l +1 j = r ; p = a [ l ];

6 do { while (a [ i ] < p) i + +; while (a [ j ] > p) j - - ; if ( i < j ) { t = a [ i ]; a [ i ] = a [ j ] ; a [ j ] = t; }

7 while ( i < j ); a [ l ] = a [ j ]; a [ j ] = p ; qsort ( a, l, j – 1) ; qsort ( a, j + 1, r ) ; }

8 ＝＞時間複雜度分析 最差情況： 若所選的pivot每次皆最小值，則執行時間

9 平均分析 假設所選的pivot將串列分成兩個子串列，其平均執行時間分別 為T(j)，和T(n-j-1)，j之值可能由1到n且機率皆相等，因此
T(n) = O(nlogn)

10 程式實例 #include <studio.h> void quick_sort ( int [ ], int ) ;
void main ( ) { int data [20] ; int size = 0, i; printf ( “\nPlease enter number to sort (enter 0 when end):\n ) ; printf ( “Number : “ ) do { scanf ( “%d “, &data [size] ); } while (data [size ++] != 0 ) ; for ( i = 0; i < 60 ; i ++ ) printf ( “－” ) ; printf ( “\nSorting : “ ); for ( I = 0; I < size ; i ++) printf ( “%d “, data [i] ); }

11 void quick_sort (int data[ ], int left, int right, int size )
{ int lbase, rbase, compare, temp, i; for (base = 1; base < size ; base ++) temp = data [base] ; compare = base ; while ( compare > 0 && data [compare – 1] > temp) data [compare] = data [compare – 1]; compare - -; } data [compare] = temp ; printf ( “Access : “) ; for ( I = 0; i < size ; i ++) printf ( “%d “, data [i]) ; printf ( “\n” ) ;

12 合併排序法 (Merge Sort)

13 定義 合併排序是一種非常重要的排序方法，由John von Neumann所提出，其原理是先把陣列分解成兩個陣列，大小相等或僅差一個元素
例如10個元素的陣列可分成兩個各含5個元素的陣列，11個元素的陣列則可分成一個含5個元素，而另一個含6個元素的陣列，一直分到不能再分為止，然後再進行排序並且合併的操作。

14 合併排序

15 合併排序最重要的一個用途是外部排序，當資料量大到無法全部讀入主記憶體裡進行排序時，可以先讀入部份資料，將這些資料排序完畢之後，再存回到輔助記憶體，它便成了有序資料，接下來分階段讀入部分有序資料進行合併排序，然後將結果存入外部記憶體，直到所有的資料排序完成為止。

16 基本運算 陣列的分解與合併排序的例子如圖所示。
在程式的設計上可考慮採用遞迴(Recursion)的方式，陣列分解完之後進行的合併排序，也就是Merge程序。 當兩個陣列已經分別排序完成，我們從兩個陣列的最小元素開始比大小，一一地拷貝到一個新的陣列中。

17 演算法 ＝＞C語言程式碼 merge_sort(int a[ ], int b[ ], int s, int m, int t) {
int i, j, k ; i = k = s ; j = m + 1 ; while ( i <= m && j <= t) if ( a [i ] <= a [ j ] ) b [ k + + ] = a [ i + + ] ; else b [ k + + ] = a [ j + + ] ;

18 while ( i <= m) b [ k + + ] = a [ i + + ] ; while ( j<= t) b [ k + + ] = a [ j + + ] for ( i = s ; i <= t ; i + + ) a [ i ] = b [i ] ; }

19 ＝＞時間複雜度分析 合併的分類是穩定的情況 其最壞與平均的時間複雜度均為O (nlogn) 所需的額外空間和檔案大小成正比。

20 程式範例－合併排序 #include <studio.h>
void select_sort ( int [ ], int ) ; void merge_sort ( int [ ], int [ ], int[ ], int, int ) ; void main ( ) { int data 1[10], data2[10], data3[20] ; int size1 = 0, size2 = 0, i; printf ( “\nPlease enter data1 to sort (enter 0 when end):\n ) ; printf ( “Number : “ )

21 do { scanf ( “%d “, &data1 [size1] ); } while (data1[size1 ++] != 0 ) ; printf ( “\nPlease enter data2 to sort (enter 0 when end):\n ) ; printf ( “Number : “ ) scanf ( “%d “, &data2 [size2] ); } while (data2[size2 ++] != 0 ) ; select_sort ( data1, --size1 ) ; select_sort ( data2, --size2 ) ;

22 for ( i = 0; i < 60 ; i ++ ) printf ( “－” ) ;
printf ( “\nData 1 : “ ) ; for ( i = 0; i < size1 ; i ++) printf ( “%d “, data1 [i] ) ; printf ( “\n” ) ; printf ( “Data2 : “) ; for ( i = 0; i < size2 ; i ++) printf ( “%d “, data2 [i] ) ; }

23 merge_sort ( data1, data2, data3, size1, size2 ) ;
for ( i = 0; i < 60 ; i ++ ) printf ( “－” ) ; printf ( “\nSorting : ” ) ; for ( i = 0 ; i < size1 +size2; i ++) printf ( “%d “, data3[i] ) ; } void select_sort ( int data [ ], int size ) { int base, compare, min, temp ;

24 for ( base = 0; base < size – 1; base ++ )
{ min = base ; for ( compare = base +1; compare < size; compare ++) if ( data [compare ] < data [ min ] ) min = compare; temp = data [min ] ; data[ min ] = data [ base ] ; data[ base ] = temp ; }

25 void merge_sort ( int data1 [ ], int data2 [ ], int data3 [ ], int size1, int size2 )
{ int arg1, arg2, arg3, I ; data1 [size1] = ; data2 [size2] = ; arg1 = 0 ; arg2 = 0 ; for ( arg3 = 0; arg3 < size1 +size2; arg3 ++)

26 if ( data1 [arg1] < data2 [arg2 ])
{ data3 [arg3] = data1 [arg1] ; arg1 ++ ; } else data3 [arg3] = data2 [arg2] ; arg2 ++ ;

27 printf ( “ Access : “ ) ; for ( i = 0 ; i < arg3 +1; i ++ ) printf ( “%d “, data3 [i] ) ; printf ( “\n” ); }