Answer Happy

Problem 2. (40 marks) Consider this algorithm: // PRE: A anarray 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 int partition(A,low, high): 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 swapA[i+1] with the pivot element at A[high] return (i+1)
1. (30 Points) Prove correctenss of partition.
2. (10 Points) Use partition to write a version of Quicksortthat sorts a numerical array A in place.