Question

Int partition(int arr[], int first, int last) {int mid = first; int pivot = arr[first]; for (int sweep = first+1; sweep <= last; sweep++) {//Assertion:. .. if (arr[sweep] < pivot) {int tmp = arr[sweep]; arr[sweep] = arr[mid+l]; arr[mid+l] = tmp; mid++;}}//Post:. .. arr[first] = arr[mid]; arr[mid] = pivot; return mid;} The focus for this problem will be the main loop of partition. You will make arguments about what it attempts to accomplish. a) The diagram depicts what we hope is the state of arr [first.. last] just after the main loop terminates [but before the pivot is swapped into place]. Write down a post-condition that effectively summarizes the values and locations of the array elements, as they relate to indices first, last and mid. Draw a similar diagram to depict the state of arr [first. .last] at the beginning of each loop. Just like the provided diagram, place all of the indices in their correct positions, and indicate anything you might know about the values of the array elements themselves. If you don't know anything about some of the array elements, then indicate that too. Write an assertion that is true at the beginning of each loop. Just like you did for part (a), it should summarize the values and locations of the array elements, as they relate to all indices, i.e., first, last, mid, but also sweep. Your answer is probably correct if, when you substitute sweep = last + 1, it matches your answer to part (a). Prove that the partition algorithm is correct using the initialization-maintenance-termination technique shown in class.