Sorting Quicksort Quicksort:Time Complexity Worst Case: T(n)=maxo≤q≤n-1(T(g)+T(n-q-1)+Θ(n) Question When would the worst case happen? The pivot is always the greatest or smallest element for each recursion. Unlucky:T(n)=O(n2)for the worst case! Lucky:worst case seldom happens! MA Jun (Institute of Computer Software) Problem Solving Apil23.2020 8/40
Sorting Quicksort Quicksort: Time Complexity Worst Case: T(n) = max0≤q≤n−1(T(q) + T(n − q − 1)) + Θ(n) Question : When would the worst case happen? The pivot is always the greatest or smallest element for each recursion. Unlucky: T(n) = O(n 2 ) for the worst case! Lucky: worst case seldom happens! MA Jun (Institute of Computer Software) Problem Solving April 23, 2020 8 / 40
Sorting Quicksort Quicksort:Time Complexity Impression Intuition: Quick sort performs quite well in practice. We usually obtain an O(nlg n)execution in most cases,rather than the worst case. WHY? PARTITION produces a mix of "good"and "bad"splits. (n-1)/2 (n-1)2 (m-12-1 (m-1)2 (a) (b) T(n)=O(nlgn) MA Jun (Institute of Computer Software) Problem Solving Api23.2020 9/40
Sorting Quicksort Quicksort: Time Complexity Impression & Intuition: Quick sort performs quite well in practice. We usually obtain an O(n lg n) execution in most cases, rather than the worst case. WHY? Partition produces a mix of “good” and “bad” splits. T(n) = O(n lg n) MA Jun (Institute of Computer Software) Problem Solving April 23, 2020 9 / 40
Sorting Quicksort Quicksort:Time Complexity Critical operation? The key cost of Quicksort comes from PARTITION The key cost of PARTITION comes from line 4. QUICKSORT(A.p.r) PARTITION(A.P.r) 1 if p<r 1 x=A[r] 2 q=PARTITION(A.p,r) 2i=p-1 3 QUICKSORT(A,p.q-1) 3 for j=p tor-1 4 QUICKSORT(A.q+1,r) 4 道A≤x 5 i=i+1 6 exchange A[i]with A[] 7 exchange A[i+1]with A[r] 8 returni+1 MA Jun (Institute of Computer Software) Problem Solving Api23.2020 10/40
Sorting Quicksort Quicksort: Time Complexity Critical operation? The key cost of Quicksort comes from Partition The key cost of Partition comes from line 4. MA Jun (Institute of Computer Software) Problem Solving April 23, 2020 10 / 40
Sorting Quicksort Quicksort Lemma(7.1) Let X be the number of comparisons performed in line 4 of PARTITION over the entire execution of QUICKSORT on an n-element array.Then the running time of QUICKSORT is O(n+X). Proof. By the discussion above,the algorithm makes at most n calls to PARTITION,each of which does a constant amount of work and then executes the for loop some number of times.Each iteration of the for loop executes line 4. 發 MA Jun (Institute of Computer Software) Problem Solving Api23.2020 11/40
Sorting Quicksort Quicksort Lemma (7.1) Let X be the number of comparisons performed in line 4 of Partition over the entire execution of Quicksort on an n-element array. Then the running time of Quicksort is O(n + X). Proof. By the discussion above, the algorithm makes at most n calls to Partition, each of which does a constant amount of work and then executes the for loop some number of times. Each iteration of the for loop executes line 4. MA Jun (Institute of Computer Software) Problem Solving April 23, 2020 11 / 40
Sorting Randomized Quicksort Randomized Quicksort Randomized Quicksort Randomized Partition RANDOMIZED-QUICKSORT(A,P.r) RANDOMIZED-PARTITION(A.P.r) 1 if p<r RANDOMIZED-PARTITION(A,P.r) 1 i=RANDOM(P.r) 3 RANDOMIZED-QUICKSORT(A,p.q-1) 2 exchange A[r]with A[i] RANDOMIZED-QUICKSORT(A.q+1,r) 3 return PARTITION(A PARTITION(A,p,r) Goal: 1 x=A[r] To compute X,the TOTAL number 2i=p-1 of comparisons performed in all calls 3 for j=p tor-1 4 if Ai<x to PARTITION. 5 i=i+1 We will NOT attempt to analyze 6 exchange A[i]with A[] how many comparisons are made in 7 exchange A[i +1]with A[r] 8 EACH call to PARTITION. return i+1 MA Jun (Institute of Computer Software) Problem Solving Api23.2020 12/40
Sorting Randomized Quicksort Randomized Quicksort Randomized Quicksort Goal: To compute X, the TOTAL number of comparisons performed in all calls to Partition. We will NOT attempt to analyze how many comparisons are made in EACH call to Partition. Randomized Partition MA Jun (Institute of Computer Software) Problem Solving April 23, 2020 12 / 40