Sorting Quicksort Quicksort:PARTITION Question How to prove the correctness of PARTITION? ≤x I unrestricted PARTITION(A,p.r) 1 x =Alr] 2 0=p-1 3 for j p tor-1 4 ifA[U]≤x i=i+1 6 exchange A[i]with A[j] 7 exchange A[i +1]with A[r] 8 return i+1 4口45，，左·生空 0a0. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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