《算法课件全121301ADA07分治法快速排序》由会员分享，可在线阅读，更多相关《算法课件全121301ADA07分治法快速排序（41页珍藏版）》请在金锄头文库上搜索。
1、2019/6/21,2,2012-2013-01 Design and Analysis of Algorithm SCUN,Review of last class,Divide and Conquer technique Master theorem The merge sort algorithm and its best-case, worst-case and average-case analysis,Divide And Conquer (II),Chapter 4,Application to sorting problem Quick sort,2019/6/21,4,201
2、2-2013-01 Design and Analysis of Algorithm SCUN,Goals of the Lecture,At the end of this lecture, you should Master the idea of quick sort algorithm Master the best-case, worst-case and average-case analysis of quick sort algorithm Master the difference between merge sort and quick sort,2019/6/21,5,2
3、012-2013-01 Design and Analysis of Algorithm SCUN,Quicksort,Another sort algorithm example to reveal the essence of divide-and-conquer technique Its idea can be described as follows: Divide: Partition the array Apr into two sub arrays Apq and Aq+1r Invariant: All elements in Apq are less than all el
4、ements in Aq+1r Conquer: Sort the two sub arrays recursively Merge: Unlike merge sort, no combining step, two sub arrays form an already-sorted array,2019/6/21,6,2012-2013-01 Design and Analysis of Algorithm SCUN,Quicksort Algorithm,ALGORITHM QuickSort(A, l, r) /Sorts a subarray by quicksort /Input:
5、 A subarray Alr of A0n-1, defined by its / left and right indices l and r /Output: Subarray Alr sorted in nondecreasing order if l r s Partition(A, l, r) /s is a split position QuickSort(A, l, s-1) QuickSort(A, s+1, r) end if,2019/6/21,7,2012-2013-01 Design and Analysis of Algorithm SCUN,Clearly, al
6、l the action takes place in the divide step should be the followings: Select a pivot and rearranges the array in place End result: Two sub arrays been separated by the pivot The elements in one sub array are smaller than the pivot The elements in another are larger than the pivot Returns the index o
7、f the “pivot” element separating the two sub arrays How do you suppose we implement this?,Partition,2019/6/21,8,2012-2013-01 Design and Analysis of Algorithm SCUN,Partition In Words,Given an array A0,n-1, we can partition the array like these: (1) Initial: select an element to act as the “pivot” (wh
8、ich?), let i and j indicate the index of second left and right elements which will be used to compare with the pivot. (2) Scan from left: Increase i until Ai greater than and equal to the pivot. (3) Scan from right: Decrease j until Aj smaller than and equal to the pivot. (4) Swap Ai and Aj (5) Repe
9、at (2),(3) and (4) until ji. (6) Swap Ai and Aj, swap A0 and Aj, return j.,2019/6/21,9,2012-2013-01 Design and Analysis of Algorithm SCUN,Partition example,Initial list,6, 7, 5, 2, 5, 8,6, 5, 5, 2, 7, 8,6, 5, 5, 2, 7, 8,Done!,2, 5, 5 6 7, 8,2019/6/21,10,2012-2013-01 Design and Analysis of Algorithm
10、SCUN,Partition Algorithm(I),ALGORITHM Partition1(A, l, r) /Input: A subarray Alr of A0n-1, defined by its left / and right indices l and r (lr) /Output: A partition of Alr, with the split position / returned as this functions value p Al i l; j r + 1 repeat repeat i i + 1 until Ai p repeat j j - 1 un
11、til Aj p swap(Ai, Aj); until i j swap(Ai, Aj) / undo last swap when i j swap(Al, Aj) return j / j is the final index of pivot,Any Problem ?,Why not “ ?,2019/6/21,11,2012-2013-01 Design and Analysis of Algorithm SCUN,Partition Algorithm(II),ALGORITHM Partition2(A, l, r) /Input: A subarray Alr of A0n-
12、1, defined by its left / and right indices l and r (lr) /Output: A partition of Alr, with the split position / returned as this functions value p Al; j l for i l +1 to r do if Ai p j j + 1 if j i swap(Aj, Ai) end if end for swap(Al, Aj) return j / j is the final index of pivot,2019/6/21,12,2012-2013
13、-01 Design and Analysis of Algorithm SCUN,Quicksort Example,2019/6/21,13,2012-2013-01 Design and Analysis of Algorithm SCUN,Analyzing Quicksort,What will be the best case for the algorithm? Partition is perfectly balanced, this means that the array is divided into two equal length subarrays. In the
14、best case: Tbest(1) = 0 Tbest(n) = 2Tbest(n/2) + n-1 What does the recurrence relation work out to? T(n) = (nlogn),2019/6/21,14,2012-2013-01 Design and Analysis of Algorithm SCUN,Analyzing Quicksort,What will be the worst case for the algorithm? Partition is always unbalanced Will any particular inp
15、ut elicit the worst case? Yes: Already-sorted input In the worst case, Partition will do n-1 comparisons, but create one partition that has n-1 elements and the other will have no elements Because we wind up just reducing the partition by one element each time, worst case is given by: T(1) = 0 T(n) = T(n - 1) + n - 1 The recurrence relation works out to T(n) = (n2),2019/6/21,15,2012-2013-01 Design and Analysis of Algorithm SCUN,Improving Quicksort,The real liability of quicksort is that it runs in O(n2
