= 2. Worst-Case Inputs for QuickSort. Consider an implemention of QuickSort where the Parti- tion() function does not re-arrange the elements that are smaller than the pivot and does not rearrange the elements that are larger than the pivot. In other words, after execution of the Par- tition() function the elements that are smaller than the pivot appear in the same order as they appeared originally, and the same holds for the elements that are larger than the pivot. For each of the following choices of the pivot element, explain how to construct a worst-case input with n elements that causes QuickSort to make a quadratic number of comparisons (that is, N(na) comparisons) in general, and give an example of such a worst-case input with n 10. It suffices to consider inputs with n elements that are permutations of the n integers {1,2, ..., n}. (a) The rightmost element of the array is chosen as pivot element. (b) The leftmost element of the array is chosen as pivot element. (c) The element in the middle of the array is chosen as pivot element. In other words, when left+right Partition(A,left,right) is called and right>left, then the element A[m] with m = is chosen as pivot element. = 2