10-11-01ADA07(分治法-快速排序)

Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,Click to edit Master title style,2024/9/14,1,Review of last class,Divide and Conquer technique,The merge sort algorithm and its,best-case,worst-case and average-case analysis,2024/9/14,2,Divide And Conquer,(II),Chapter 4,Application to sorting problem,Quick sort,2024/9/14,3,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,Understand the difference between merge sort and quick sort,2024/9/14,4,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 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 array,2024/9/14,5,Quicksort Algorithm,ALGORITHM QuickSort(,A,l,r,),/Sorts a subarray by quicksort,/Input: A subarray,A,l,r, of,A,0,n,-1, defined by its,/ left and right indices,l,and,r,/Output: Subarray,A,l,r, 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,2024/9/14,6,Clearly, all 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 of the “pivot” element separating the two sub arrays,How do you suppose we implement this?,Partition,2024/9/14,7,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” (,which,?), 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 A,i, greater than and equal to the pivot.,(3) Scan from right: Decrease,j,until A,j, smaller than and equal to the pivot.,(4) Swap A,i, and A,j,(5) Repeat (2),(3) and (4) until,j,i,.,(6) Swap A,i, and A,j, swap A0 and A,j, return,j,.,2024/9/14,8,Partition example,Initial list,6,7, 5, 2, 5, 8,6,7, 5, 2,5, 8,6, 5, 5, 2, 7, 8,6, 5, 5,2, 7, 8,Done!,Quciksort is not stable,6,7, 5, 2, 5, 8,2, 5, 5 6 7, 8,2024/9/14,9,Partition Algorithm(I),ALGORITHM Partition1(,A,l,r,),/Input: A subarray,A,l,r, of,A,0,n,-1, defined by its left,/ and right indices,l,and,r,(,l,r,),/Output: A partition of,A,l,r, with the split position,/ returned as this functions value,p,A,l,i,l,;,j,r,+ 1,repeat,repeat,i,i,+ 1,until,A,i, ,p,repeat,j,j,- 1,until,A,j,p,swap(A,i, A,j,);,until,i,j,swap(A,i, A,j,),/ undo last s,i,j,swap(A,l, A,j,return,j,/,j,is the final index of pivot,Any Problem ?,2024/9/14,10,Partition Algorithm(II),ALGORITHM Partition2(,A,l,r,),/Input: A subarray,A,l,r, of,A,0,n,-1, defined by its left,/ and right indices,l,and,r,(,l,r,),/Output: A partition of,A,l,r, with the split position,/ returned as this functions value,p,A,l,;,j,l,for,i,l,+1 to,r,do,if,A,i,p,j,j +,1,if,j,i,swap(A,j, A,i,),end,if,end,for,swap(A,l, A,j,),return,j,/,j,is the final index of pivot,Why not “,“ ?,2024/9/14,11,Quicksort Example,2024/9/14,12,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 best case:,T,best,(1) = 0,T,best,(,n,) = 2T,best,(,n,/2) +,n,-1,What does the recurrence relation work out to?,T(n) = (,n,log,n,),2024/9/14,13,Analyzing Quicksort,What will be the worst case for the algorithm?,Partition is always unbalanced,Will any particular input 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,) = (,n,2,),2024/9/14,14,Improving Quicksort,The real liability of quicksort is that it runs in O(,n,2,) on already-sorted input,Discusses two solutions:,Randomize the input array, OR,Pick a random pivot element,How will these solve the problem?,By insuring that no particular input can be chosen to make quicksort run in O(,n,2,) time,2024/9/14,15,Analyzing Quicksort: Average Case,Assuming random input, average-case running time is much closer to,(,n,log,n,) than O(,n,2,),First, 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(9,n,/10) + T(,n,/10) +,n,-1,How deep will the recursion go?,(draw it),2024/9/14,16,Analyzing Quicksort: Average Case,Intuitively, 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 node, then good-split the resulting size,(,n-,1),node?,2024/9/14,17,Analyzing Quicksort: Average Case,Intuitively, 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 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 = 2,n,-3 = O(,n,),No worse than if we had good-split the root node!,2024/9/14,18,Analyzing Quicksort: Average Case,Intuitively, 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 split,Thus running time of alternating bad and good splits is still O(,n,log,n,), with slightly higher constants,How can we be more rigorous?,2024/9/14,19,Analyzing Quicksort: Average Case,For simplicity, assume:,All inputs distinct (no repeats),Slightly different,partition,procedure,partition around a random element, which is not included in subarrays,all splits (0:,n,-1, 1:,n,-2, 2:,n,-3, ,n,-1:0) equally likely,What is the probability of a particular split happening?,Answer: 1/,n,2024/9/14,20,Analyzing Quicksort: Average Case,So partition generates splits (0:,n,-1, 1:,n,-2, 2:,n,-3, ,n,-2:1,n,-1:0) each with probability 1/,n,If T(,n,) is the expected running time,What is each term under the summation for?,What is the,(,n,),term for?,2024/9/14,21,Analyzing Quicksort: Average Case,So,2024/9/14,22,Analyzing Quicksort: Average Case,We 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,n,2024/9/14,23,Analyzing Quicksort: Average Case,We can solve this recurrence using the dreaded substitution method,Guess the answer,Whats the answer?,Assume that the inductive hypothesis holds,Substitute it in for some value ,n,Prove that it follows for,n,2024/9/14,24,Analyzing Quicksort: Average Case,We can solve this recurrence using the dreaded substitution method,Guess the answer,T(,n,) =,(,n,log,n,),Assume that the inductive hypothesis holds,Substitute it in for some value ,n,Prove that it follows for,n,2024/9/14,25,Analyzing Quicksort: Average Case,We can solve this recurrence using the dreaded substitution method,Guess the answer,T(,n,) =,(,n,log,n,),Assume that the inductive hypothesis holds,Whats the inductive hypothesis?,Substitute it in for some value ,n,Prove that it follows for,n,2024/9/14,26,Analyzing Quicksort: Average Case,We can solve this recurrence using the dreaded substitution method,Guess the answer,T(,n,) =,(,n,log,n,),Assume that the inductive hypothesis holds,T(,n,),an,log,n,+,b,for some constants,a,and,b,Substitute it in for some value ,n,Prove that it follows for,n,2024/9/14,27,Analyzing Quicksort: Average Case,We can solve this recurrence using the dreaded substitution method,Guess the answer,T(,n,) =,(,n,log,n,),Assume that the inductive hypothesis holds,T(,n,),an,log,n,+,b,for some constants,a,and,b,Substitute it in for some value ,n,What value?,Prove that it follows for,n,2024/9/14,28,Analyzing Quicksort: Average Case,We can solve this recurrence using the dreaded substitution method,Guess the answer,T(,n,) =,(,n,log,n,),Assume that the inductive hypothesis holds,T(,n,),an,log,n,+,b,for some constants,a,and,b,Substitute it in for some value ,n,The value,k,in the recurrence,Prove that it follows for,n,2024/9/14,29,What are we doing here?,Analyzing Quicksort: Average Case,The recurrence to be solved,What are we doing here?,What are we doing here?,Plug in inductive hypothesis,Expand out the k=0 case,2b/n is just a constant, so fold it into,(n),2024/9/14,30,What are we doing here?,What are we doing here?,Evaluate the summation: b+b+b = b (n-1),The recurrence to be solved,Since n-1n, 2b(n-1)/n 2b,Analyzing Quicksort: Average Case,What are we doing here?,Distribute the summation,This summation gets its own set of slides later,2024/9/14,31,How 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 + b,What the hell?,Well prove this later,What are we doing here?,Distribute the (2a/n) term,The recurrence to be solved,Analyzing Quicksort: Average Case,2024/9/14,32,Analyzing Quicksort: Average Case,So T(,n,),an,log,n,+,b,for certain,a,and,b,Thus the induction holds,Thus T(,n,) =,(,n,log,n,),Thus quicksort runs in,(,n,log,n,) time on average (phew!),Oh yeah, the summation,2024/9/14,33,What are we doing here?,The,log,k in the second term is bounded by,log,n,Tightly Bounding of the Key Summation,What are we doing here?,Move the,log,n outside the summation,What are we doing here?,Split the summation for a tighter bound,2024/9/14,34,The summation bound so far,Tightly Bounding of the Key Summation,What are we doing here?,The,log,k in the first term is bounded by,log,n/2,What are we doing here?,log,n/2 =,log,n,- 1,What are we doing here?,Move (,log,n,- 1,) outside the summation,2024/9/14,35,The summation bound so far,Tightly Bounding of the Key Summation,What are we doing here?,Distribute the (,log,n,- 1,),What are we doing here?,The summations overlap in range; combine them,What are we doing here?,The Guassian series,2024/9/14,36,The summation bound so far,Tightly Bounding of the Key Summation,What are we doing here?,Rearrange first term, place upper bound on second,What are we doing?,X Guassian series,What are we doing?,Multiply it all out,2024/9/14,37,Tightly Bounding of the Key Summation,2024/9/14,38,The difference between merge sort and quick sort,Divide:,Merge sort: divides its inputs element according to their position in the array,Quick sort: divides its inputs element according to their value.,Combine:,Merge sort: merges two sorted lists into one ordered list,Quick sort: no need to merge,Worst case,Average case,Stability,In place,2024/9/14,39,The End,2024/9/14,40,Assignments,Reading Assignment: Textbook page 142-147,Exercises: No 3,5,6,8 of section 4.2,2024/9/14,41,