1. Shaker sort is a bi-directional bubble sort. The shaker sort algorithm is: begin o, end A.length-1 // At the beginning of every iteration of this loop, we know that the // elements in A are in their final sorted positions from A[0] to A[begin-1] /I and from Alend+1 to the end of A. That means that Albegin] to A(end] are /I still to be sorted do for i going from begin to end-1 end-- if no swaps occurred during the preceding for loop, the sort is done for i going from end to begin+l begintt if Ali and Alit1) are out of order, swap them if A(] and A[i-1] are out of order, swap them until no swaps have occurred or begin- end Part A: What is the best-case time complexity of shaker sort? Briefly explain the reasoning behind your answer. The best-case behavior would be achieved if the values in the array were (complete this part of the description). Part B: What is the worst-case time complexity of shaker sort? Briefly explain the reasoning behind your answer. The worst-case behavior would be achieved if the values in the array were (complete this part of the description)