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/40Sorting 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