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