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