算法设计(分治法-快速排序)

1、2022-4-2622009-2010-01 Design and Analysis of Algorithm SCUECReview of last classbDivide and Conquer techniquebThe merge sort algorithm and its best-case, worst-case and average-case analysisDivide And Conquer(II)Chapter 42022-4-2642009-2010-01 Design and Analysis of Algorithm SCUECGoals of the Lect

2、urebAt 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 Understand the difference between merge sort and quick sort2022-4-2652009-2010-01 Design and Analysis of Algorithm SCUECQuicksortbAnot

3、her sort algorithm example to reveal the essence of divide-and-conquer techniquebIts idea can be described as follows: Divide: Partition the array Ap.r into two sub arrays Ap.q and Aq+1.r Invariant: All elements in Ap.q are less than all elements in Aq+1.r Conquer: Sort the two sub arrays recursivel

4、y Merge: Unlike merge sort, no combining step, two sub arrays form an already-sorted array2022-4-2662009-2010-01 Design and Analysis of Algorithm SCUECQuicksort AlgorithmALGORITHM QuickSort(A, l, r)/Sorts a subarray by quicksort/Input: A subarray Alr of A0n-1, defined by its/ left and right indices

5、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 if2022-4-2672009-2010-01 Design and Analysis of Algorithm SCUECbClearly, all the action takes place in the divide step should be the followings:

6、 Select a pivot and rearranges the array in place End result: Two sub arrays been separated by the pivotThe elements in one sub array are smaller than the pivotThe elements in another are larger than the pivot Returns the index of the “pivot” element separating the two sub arraysbHow do you suppose

7、we implement this?Partition2022-4-2682009-2010-01 Design and Analysis of Algorithm SCUECPartition In WordsbGiven an array A0,n-1, we can partition the array like these: (1) Initial: select an element to act as the “pivot” (which?), let i and j indicate the index of second left and right elements whi

8、ch 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) Repeat (2),(3) and (4) until ji. (6) Swap Ai and Aj, swap A0 and Aj, return j.2

9、022-4-2692009-2010-01 Design and Analysis of Algorithm SCUECPartition example Initial list6, 7, 5, 2, 5, 8ji6, 7, 5, 2, 5, 8ji6, 5, 5, 2, 7, 8ji6, 5, 5, 2, 7, 8jiDone!QuciksortQuciksort is not stable is not stable6, 7, 5, 2, 5, 82, 5, 5 6 7, 82022-4-26102009-2010-01 Design and Analysis of Algorithm

10、SCUECPartition 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 valuep Al i l; j r + 1 repeat repeat i i + 1 until Ai p repeat j j - 1 unti

11、l Aj p swap(Ai, Aj); until i j swap(Ai, Aj) / undo last swap when i j swap(Al, Ajreturn j / j is the final index of pivot Any Problem ?2022-4-26112009-2010-01 Design and Analysis of Algorithm SCUECPartition Algorithm(II)ALGORITHM Partition1(A, l, r) /Input: A subarray Alr of A0n-1, defined by its le

12、ft / and right indices l and r (lr) /Output: A partition of Alr, with the split position / returned as this functions valuep 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 forswap(Al, Aj)return j / j is the final index of pivot Why not “ ?2022-4-26122009-2010-01 Design and

13、 Analysis of Algorithm SCUECQuicksort Example5 8 4 9 3 6 7 2 initial array 2 4 3 5 8 6 7 9 the first partition 2 4 3 5 8 6 7 9 the second partition 2 3 4 5 8 6 7 9 the third partition 2 3 4 5 8 6 7 9 the fourth partition 2 3 4 5 7 6 8 9 the fifth partition 2 3 4 5 6 7 8 9 the sixth partition 2 3 4 5

14、 6 7 8 9 the seventh partition 2 3 4 5 6 7 8 9 the eighth partition 2022-4-26132009-2010-01 Design and Analysis of Algorithm SCUECAnalyzing QuicksortbWhat will be the best case for the algorithm? Partition is perfectly balanced, this means that the array is divided into two equal length subarrays.bI

15、n the best case:Tbest(1) = 0Tbest(n) = 2Tbest(n/2) + n-1bWhat does the recurrence relation work out to?T(n) = (nlogn) 2022-4-26142009-2010-01 Design and Analysis of Algorithm SCUECAnalyzing QuicksortbWhat will be the worst case for the algorithm? Partition is always unbalancedbWill any particular in

16、put elicit the worst case? Yes: Already-sorted inputbIn the worst case, Partition will do n-1 comparisons, but create one partition that has n-1 elements and the other will have no elementsbBecause we wind up just reducing the partition by one element each time, worst case is given by:T(1) = 0T(n) =

17、 T(n - 1) + n - 1bThe recurrence relation works out to T(n) = (n2)2022-4-26152009-2010-01 Design and Analysis of Algorithm SCUEC Improving QuicksortbThe real liability of quicksort is that it runs in O(n2) on already-sorted inputbDiscusses two solutions: Randomize the input array, OR Pick a random p

18、ivot elementbHow will these solve the problem? By insuring that no particular input can be chosen to make quicksort run in O(n2) time2022-4-26162009-2010-01 Design and Analysis of Algorithm SCUECAnalyzing Quicksort: Average CasebAssuming random input, average-case running time is much closer to (nlo

19、gn) than O(n2)bFirst, a more intuitive explanation/example: Suppose that partition always produces a 9-to-1 split. This looks quite unbalanced! The recurrence is thus:T(n) = T(9n/10) + T(n/10) + n-1How deep will the recursion go? (draw it)2022-4-26172009-2010-01 Design and Analysis of Algorithm SCUE

20、CAnalyzing Quicksort: Average CasebIntuitively, a real-life run of quicksort will produce a mix of “bad” and “good” splits Randomly distributed among the recursion tree Pretend for intuition that they alternate between best-case (n/2 : n/2) and worst-case (n-1 : 0) What happens if we bad-split root

21、node, then good-split the resulting size (n-1) node?2022-4-26182009-2010-01 Design and Analysis of Algorithm SCUECAnalyzing Quicksort: Average CasebIntuitively, a real-life run of quicksort will produce a mix of “bad” and “good” splits Randomly distributed among the recursion tree Pretend for intuit

22、ion that they alternate between best-case (n/2 : n/2) and worst-case (n-1 : 0) What happens if we bad-split root node, then good-split the resulting size (n-1) node? We end up with three subarrays, size 0, (n-1)/2, (n-1)/2 Combined cost of splits = n-1 + n -2 = 2n -3 = O(n) No worse than if we had g

23、ood-split the root node!2022-4-26192009-2010-01 Design and Analysis of Algorithm SCUECAnalyzing Quicksort: Average CasebIntuitively, the O(n) cost of a bad split (or 2 or 3 bad splits) can be absorbed into the O(n) cost of each good splitbThus running time of alternating bad and good splits is still

24、 O(nlogn), with slightly higher constantsbHow can we be more rigorous?2022-4-26202009-2010-01 Design and Analysis of Algorithm SCUECAnalyzing Quicksort: Average CasebFor simplicity, assume: All inputs distinct (no repeats) Slightly different partition procedurepartition around a random element, whic

25、h is not included in subarraysall splits (0:n-1, 1:n-2, 2:n-3, , n-1:0) equally likelybWhat is the probability of a particular split happening?bAnswer: 1/n2022-4-26212009-2010-01 Design and Analysis of Algorithm SCUECAnalyzing Quicksort: Average CasebSo partition generates splits (0:n-1, 1:n-2, 2:n-

26、3, , n-2:1, n-1:0) each with probability 1/nbIf T(n) is the expected running time,bWhat is each term under the summation for?bWhat is the (n) term for? 1011( )nkT nT kT nknn 2022-4-26222009-2010-01 Design and Analysis of Algorithm SCUECAnalyzing Quicksort: Average CasebSo 101011121nknkT nT kT nknnT

27、knn 2022-4-26232009-2010-01 Design and Analysis of Algorithm SCUECAnalyzing Quicksort: Average CasebWe can solve this recurrence using the dreaded substitution method Guess the answer Assume that the inductive hypothesis holds Substitute it in for some value n Prove that it follows for n2022-4-26242

28、009-2010-01 Design and Analysis of Algorithm SCUECAnalyzing Quicksort: Average CasebWe can solve this recurrence using the dreaded substitution method Guess the answerWhats the answer? Assume that the inductive hypothesis holds Substitute it in for some value n Prove that it follows for n2022-4-2625

29、2009-2010-01 Design and Analysis of Algorithm SCUECAnalyzing Quicksort: Average CasebWe can solve this recurrence using the dreaded substitution method Guess the answerT(n) = (nlogn) Assume that the inductive hypothesis holds Substitute it in for some value n Prove that it follows for n2022-4-262620

30、09-2010-01 Design and Analysis of Algorithm SCUECAnalyzing Quicksort: Average CasebWe can solve this recurrence using the dreaded substitution method Guess the answerT(n) = (nlogn) Assume that the inductive hypothesis holdsWhats the inductive hypothesis? Substitute it in for some value n Prove that

31、it follows for n2022-4-26272009-2010-01 Design and Analysis of Algorithm SCUECAnalyzing Quicksort: Average CasebWe can solve this recurrence using the dreaded substitution method Guess the answerT(n) = (nlogn) Assume that the inductive hypothesis holdsT(n) anlogn + b for some constants a and b Subst

32、itute it in for some value n Prove that it follows for n2022-4-26282009-2010-01 Design and Analysis of Algorithm SCUECAnalyzing Quicksort: Average CasebWe can solve this recurrence using the dreaded substitution method Guess the answerT(n) = (nlogn) Assume that the inductive hypothesis holdsT(n) anl

33、ogn + b for some constants a and b Substitute it in for some value nWhat value? Prove that it follows for n2022-4-26292009-2010-01 Design and Analysis of Algorithm SCUECAnalyzing Quicksort: Average CasebWe can solve this recurrence using the dreaded substitution method Guess the answerT(n) = (nlogn)

34、 Assume that the inductive hypothesis holdsT(n) anlogn + b for some constants a and b Substitute it in for some value nThe value k in the recurrence Prove that it follows for n2022-4-26302009-2010-01 Design and Analysis of Algorithm SCUECWhat are we doing here?Analyzing Quicksort: Average Case 10101

35、1111122log2log22log2lognknknknknkT nT knnakkbnnbakkbnnbakkbnnnakkbnn The recurrence to be solvedWhat are we doing here?What are we doing here?Plug in inductive hypothesisExpand out the k=0 case2b/n is just a constant, so fold it into (n)2022-4-26312009-2010-01 Design and Analysis of Algorithm SCUECW

36、hat are we doing here?What are we doing here?Evaluate the summation: b+b+b = b (n-1)The recurrence to be solvedSince n-1n, 2b(n-1)/n 2bAnalyzing Quicksort: Average Case 11111111112log22log22log(1)2log2nknnkknknkT nakkbnnakkbnnnabkknnnnakkbnn What are we doing here?Distribute the summationThis summat

37、ion gets its own set of slides later2022-4-26322009-2010-01 Design and Analysis of Algorithm SCUECHow did we do this?Pick a large enough thatan/4 dominates (n)+b What are we doing here?Remember, our goal is to get T(n) an log n + bWhat the hell?Well prove this laterWhat are we doing here?Distribute

38、the (2a/n) termThe recurrence to be solvedAnalyzing Quicksort: Average Case 11222log2211log228log24log4lognkaT nkkbnnannnbnnaannnbnaannbnbnannb 2022-4-26332009-2010-01 Design and Analysis of Algorithm SCUECAnalyzing Quicksort: Average CasebSo T(n) an log n + b for certain a and b Thus the induction

39、holds Thus T(n) = (nlogn) Thus quicksort runs in (nlogn) time on average (phew!)bOh yeah, the summation 2022-4-26342009-2010-01 Design and Analysis of Algorithm SCUECWhat are we doing here?The log k in the second term is bounded by log nTightly Bounding of the Key Summation21111122111221112logloglog

40、loglogloglognnnkkknnnkknnnkknkkkkkkkkknkknkWhat are we doing here?Move the log n outside the summationWhat are we doing here?Split the summation for a tighter bound2022-4-26352009-2010-01 Design and Analysis of Algorithm SCUECThe summation bound so farTightly Bounding of the Key Summation21111122111

41、22111221112loglogloglog2loglog1loglog1lognnnkkknnnkknnnkknnnkknkkkknkknnkknnknknkWhat are we doing here?The log k in the first term is bounded by log n/2What are we doing here?log n/2 = log n - 1What are we doing here?Move (log n - 1) outside the summation2022-4-26362009-2010-01 Design and Analysis of Algorithm SCUECThe