Prove this algorithm for in-place quicksort is correct using induction. Also include the loop invariant proof:

Algorithm inPlacePartition(S, a, b): Input: An array, S, of distinct elements: integers a and b such that a lessthanorequalto b Output: An integer, l, such that the subarray S[a b] is partitioned into S[a..l - 1] and S[l..b] so that every element in S[a..l - 1] is less than each element in S[l..b] Let r be a random integer in the range [a, b] Swap S[r] and S[b] p leftarrow S[b] // the pivot l leftarrow a // l will scan rightward r leftarrow b - 1 // r will scan leftward while l lessthanorequalto r do // find an element larger than the pivot while l lessthanorequalto r and S[l] lessthanorequalto p do l leftarrow l + 1 while r greaterthanorequalto l and S[r] greaterthanorequalto p do // find an element smaller than the pivot r leftarrow r - 1 if l