Sorting Quicksort Quicksort:PARTITION Question How to prove the correctness of PARTITION? ≤x unrestricted PARTITION(A,p.r) At the beginning of each iteration of x= A[r] the loop of lines 3-6,for any array 2 0=p-1 index k,we have: 3 for j=p tor- 4 fA[U]≤x L.Ifp≤k≤i,then A[k≤x. 5 i=i+1 2.Ifi+1≤k≤j-l,then A[k]>x. 6 exchange A[i]with A[j] 3.If k =r,then A[k]=x. 7 exchange A+I]with Ar] 8 return i+1 MA Jun (Institute of Computer Software) Problem Solving Apil23.2020 3/40
Sorting Quicksort Quicksort: Partition k Question : How to prove the correctness of Partition? At the beginning of each iteration of the loop of lines 3-6, for any array index k, we have: MA Jun (Institute of Computer Software) Problem Solving April 23, 2020 3 / 40
Sorting Quicksort Quicksort:Time Complexity Question What is the time complexity of QUICKSORT? QUICKSORT(A,p,r) 1 ifp<r 2 PARTITION(A,p.r) 3 QUICKSORT(A.p.q-1) 4 QUICKSORT(A,q +1,r) The recurrence:T(n)=T(m)+T(n2)+cn where: m=9-1-p+1=q-p 2=r-(q+1)+1=r-q m+n2=r-p initially,p=1,r =n m,n2 vary and depend on q=PARTITION(A,p,r) MA Jun (Institute of Computer Software) Problem Solving Api23.2020 4/40
Sorting Quicksort Quicksort: Time Complexity Question : What is the time complexity of Quicksort? The recurrence: T(n) = T(n1) + T(n2) + cn where: n1 = q − 1 − p + 1 = q − p n2 = r − (q + 1) + 1 = r − q n1 + n2 = r − p initially, p = 1,r = n n1, n2 vary and depend on q = Partition(A, p,r) MA Jun (Institute of Computer Software) Problem Solving April 23, 2020 4 / 40
Sorting Quicksort Quicksort:Time Complexity Question:Which factor would affect the efficiency of QUICKSORT? always produces a 9-to-1 split cn 品n cn logion 品n 品n cn 0g10/9T 8品n 恐n 4aa444, cn ≤C刀 the choice of Pivot would affect the tree height. w≤C刀 O(n Ign) MA Jun (Institute of Computer Software) Problem Solving Aprl23.2020 5/40
Sorting Quicksort Quicksort: Time Complexity Question : Which factor would affect the efficiency of Quicksort? always produces a 9-to-1 split the choice of Pivot would affect the tree height. MA Jun (Institute of Computer Software) Problem Solving April 23, 2020 5 / 40
Sorting Quicksort Quicksort:Time Complexity Question:Which factor would affect the efficiency of QUICKSORT? always produces a 9-to-1 split cn 9 cn logion 品n 品n cn 0g10/9 Too 11 cn / any split of constant proportionality ≤CI o tree height:(Ig n) o cost of each level:cn u≤Cn o total running time: O(nlgn) O(n Ign) MA Jun (Institute of Computer Software) Problem Solving Apil23.2020 6/40
Sorting Quicksort Quicksort: Time Complexity Question : Which factor would affect the efficiency of Quicksort? always produces a 9-to-1 split any split of constant proportionality tree height: Θ(lg n) cost of each level: cn total running time: O(n lg n) MA Jun (Institute of Computer Software) Problem Solving April 23, 2020 6 / 40
Sorting Quicksort Quicksort:Time Complexity Question Which factor would affect the efficiency of QUICKSORT? cn 品n cn 10g10刀 品n n号目力： cn /N 0g10/97 品n 729 10o0H cn any split of9Npfr州 nn…≤C刀 What is the WORST CASE? uu≤C刀 T(n)=maxosqsn-1(T(q)+T(n-q-1))+e(n) O(nlgn) MA Jun (Institute of Computer Software) Problem Solving Apil23.2020 7/40
Sorting Quicksort Quicksort: Time Complexity Question : Which factor would affect the efficiency of Quicksort? any split of ///////////////////////////// constant proportionality What is the WORST CASE? T(n) = max0≤q≤n−1(T(q) + T(n − q − 1)) + Θ(n) MA Jun (Institute of Computer Software) Problem Solving April 23, 2020 7 / 40