Consider this algorithm: // PRE: A an array of numbers, initially low = 0, high = size of A - 1 // POST: Returns the position of the pivot, and A is partitioned with elements to the left of the pivot being <= pivot, // // and elements to the right of the pivot being >=pivot int partition (A, low, high): 1. 2. pivot =A[high] i = low-1 for j from low to (high-1) do: if pivot >A[j] then do: i = i + 1 swap A[j] with A[i] swap A[i+1] with the pivot element at A [high] return (i+1) Prove correctenss of partition. Use partition to write a version of Quicksort that sorts a numerical array A in place.

Consider this algorithm: // PRE: A an array of numbers, initially low = 0, high = size of A - 1 // POST: Returns the position of the pivot, and A is partitioned with elements to the left of the pivot being <= pivot, // // and elements to the right of the pivot being >=pivot int partition (A, low, high): 1. 2. pivot =A[high] i = low-1 for j from low to (high-1) do: if pivot >A[j] then do: i = i + 1 swap A[j] with A[i] swap A[i+1] with the pivot element at A [high] return (i+1) Prove correctenss of partition. Use partition to write a version of Quicksort that sorts a numerical array A in place.