Consider the following variation of PARTITION (for Quicksort) due to N. Lomuto. To partition A[p..r], this version grows two regions, A[p..i] and A[i+1 .j] such that every element in the first region is less than or equal to x = A[r] and every element in the second region is greater than x. LAMUTO-PARTITONG(A, p, r) x leftarrow A[r] i leftarrow p-1 for j leftarrow p ti r di if A[j] lessthanorequalto x then i leftarrow i + 1 exchange A[i] doubleheadarrow A[j] if i