Suppose we want to sort an array in ascending order and we implement quicksort so that we always choose the last element in the array as the pivot element. Assume that the input is a permutation of {1, 2, …, n}. Which of the following would definitely be a worst case permutation of this input for this implementation of quicksort?
{1, 2,…, n} with all even numbers in random order followed by all odd numbers in random order.
{1, 2, . . . , n} in ascending order.
{1,2,...,n} in some random order.
{1, 2, . . . , n} with all odd numbers in ascending order followed by all even numbers in random order.
