Sorting Quicksort Quicksort:PARTITION Question How to prove the correctness of PARTITION? ≤x unrestricted PARTITION(A,p.r) 1 x A[r] 2 0=p-1 for=p tor-1 4 tA[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口4步，，左·生，空 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