101101ADA07分治法快速排序

1、2022-3-2212022-3-222Review of last classbDivide and Conquer techniquebThe merge sort algorithm and its best-case, worst-case and average-case analysis2022-3-223Divide And Conquer(II)Chapter 42022-3-224Goals of the LecturebAt the end of this lecture, you should Master the idea of quick sort algorithm

2、 Master the best-case, worst-case and average-case analysis of quick sort algorithm Understand the difference between merge sort and quick sort2022-3-225QuicksortbAnother sort algorithm example to reveal the essence of divide-and-conquer techniquebIts idea can be described as follows: Divide: Partit

3、ion 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 recursively Merge: Unlike merge sort, no combining step, two sub arrays form an already-sorted array2022-3-226Quicksort AlgorithmALGORITHM Quic

4、kSort(A, l, r)/Sorts a subarray by quicksort/Input: 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 if2022-3-227bClearly, all th

5、e 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 pivotThe elements in one sub array are smaller than the pivotThe elements in another are larger than the pivot Returns the index of the

6、“pivot” element separating the two sub arraysbHow do you suppose we implement this?Partition2022-3-228Partition 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 righ

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

8、Aj, return j.2022-3-229Partition example Initial list6, 7, 5, 2, 5, 8ji6, 7, 5, 2, 5, 8ji6, 5, 5, 2, 7, 8ji6, 5, 5, 2, 7, 8jiDone!Quciksort is not stableQuciksort is not stable6, 7, 5, 2, 5, 82, 5, 5 6 7, 82022-3-2210Partition Algorithm(I)ALGORITHM Partition1(A, l, r) /Input: A subarray Alr of A0n-1

9、, 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 until Aj p swap(Ai, Aj); until i j swap(Ai, Aj) / undo last s i j swap(Al, Ajreturn j / j is

10、 the final index of pivot Any Problem ?2022-3-2211Partition Algorithm(II)ALGORITHM Partition2(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; j l for i l +1 to

11、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-3-2212Quicksort 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

12、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 6 7 8 9 the seventh partition 2 3 4 5 6 7 8 9 the eighth partition 2022-3-2213Analyzing QuicksortbWhat will be the best case for the algorithm? Partition is perfectly balanced, this means that the

13、array is divided into two equal length subarrays.bIn the best case:Tbest(1) = 0Tbest(n) = 2Tbest(n/2) + n-1bWhat does the recurrence relation work out to?T(n) = (nlogn) 2022-3-2214Analyzing QuicksortbWhat will be the worst case for the algorithm? Partition is always unbalancedbWill any particular in

14、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) =

15、 T(n - 1) + n - 1bThe recurrence relation works out to T(n) = (n2)2022-3-2215 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 pivot elementbHow will these solve the problem? By i

16、nsuring that no particular input can be chosen to make quicksort run in O(n2) time2022-3-2216Analyzing Quicksort: Average CasebAssuming random input, average-case running time is much closer to (nlogn) than O(n2)bFirst, a more intuitive explanation/example: Suppose that partition always produces a 9

17、-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-3-2217Analyzing Quicksort: Average CasebIntuitively, a real-life run of quicksort will produce a mix of “bad” and “good” splits Randomly distributed among the

18、 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 node, then good-split the resulting size (n-1) node?2022-3-2218Analyzing Quicksort: Average CasebIntuitively, a real-life run of quicksort will produce a

19、 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 node, then good-split the resulting size (n-1) node? We end up with three subarrays, size 0

20、, (n-1)/2, (n-1)/2 Combined cost of splits = n-1 + n -2 = 2n -3 = O(n) No worse than if we had good-split the root node!2022-3-2219Analyzing 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 tim

21、e of alternating bad and good splits is still O(nlogn), with slightly higher constantsbHow can we be more rigorous?2022-3-2220Analyzing Quicksort: Average CasebFor simplicity, assume: All inputs distinct (no repeats) Slightly different partition procedurepartition around a random element, which is n

22、ot 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-3-2221Analyzing Quicksort: Average CasebSo partition generates splits (0:n-1, 1:n-2, 2:n-3, , n-2:1, n-1:0) each with probability 1/nbIf T(n) is t

23、he expected running time,bWhat is each term under the summation for?bWhat is the (n) term for? 1011( )nkT nT kT nknn 2022-3-2222Analyzing Quicksort: Average CasebSo 101011121nknkT nT kT nknnT knn 2022-3-2223Analyzing Quicksort: Average CasebWe can solve this recurrence using the dreaded substitution

24、 method Guess the answer Assume that the inductive hypothesis holds Substitute it in for some value n Prove that it follows for n2022-3-2224Analyzing Quicksort: Average CasebWe can solve this recurrence using the dreaded substitution method Guess the answerWhats the answer? Assume that the inductive

25、 hypothesis holds Substitute it in for some value n Prove that it follows for n2022-3-2225Analyzing 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 P

26、rove that it follows for n2022-3-2226Analyzing 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 it follows f

27、or n2022-3-2227Analyzing 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 Substitute it in for some value n Prove that it follows for n2022-3-

28、2228Analyzing 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 Substitute it in for some value nWhat value? Prove that it follows for n2022-3-

29、2229Analyzing 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 Substitute it in for some value nThe value k in the recurrence Prove that it fo

30、llows for n2022-3-2230What are we doing here?Analyzing Quicksort: Average Case 101011111122log2log22log2lognknknknknkT 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

31、, so fold it into (n)2022-3-2231What 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?Di

32、stribute the summationThis summation gets its own set of slides later2022-3-2232How 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 the (2a/n) termThe

33、 recurrence to be solvedAnalyzing Quicksort: Average Case 11222log2211log228log24log4lognkaT nkkbnnannnbnnaannnbnaannbnbnannb 2022-3-2233Analyzing Quicksort: Average CasebSo T(n) an log n + b for certain a and b Thus the induction holds Thus T(n) = (nlogn) Thus quicksort runs in (nlogn) time on aver

34、age (phew!)bOh yeah, the summation 2022-3-2234What are we doing here?The log k in the second term is bounded by log nTightly Bounding of the Key Summation21111122111221112logloglogloglogloglognnnkkknnnkknnnkknkkkkkkkkknkknkWhat are we doing here?Move the log n outside the summationWhat are we doing

35、here?Split the summation for a tighter bound2022-3-2235The summation bound so farTightly Bounding of the Key Summation2111112211122111221112loglogloglog2loglog1loglog1lognnnkkknnnkknnnkknnnkknkkkknkknnkknnknknkWhat 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-3-2236The