(2) (20 pts) Cocktail-shaker sort is a variant of bubblesort. On odd num- bered passes through the list, you run a standard pass of bubblesort (as in bubble the smallest from right to the left). On even numbered passes through the list, you run a "left to right version of bubblesort, carrying the largest element you have seen from the left side of the list down and inverting it with the next element examined if it is out of order. For example, consider the input 2 9178 3. After the first pass, the list is 1 293 7 8 , exactly like bubblesort. After the second pass, the list is 1 2 3 7 8 9. Also, we stop if no changes were made during the previous pass. Note: Use 1 through n as input for this problem. So, 1 2 3 ... (n- 1) n would be an input of size n. Another such input is 2 1 3 4 5 (n- 1) n. In contrast, 1 2 3 4 5 is an input of size just 5. If the input are really integers in the range 1 through n, there are better sorting algorithms to use. But, that is not the point here. (a) Write pseudo-code for cocktail-shaker-sort (A, n) where A is the array A[1] through A[n]. (b) Even though bubblesort and cocktail-shaker sort are very similar, their running times can be quite different on specific inputs. Give a specific input of size n on which cocktail-shaker sort runs significantly faster than bubble-sort, i.e., on that input, the time taken by cocktail-shaker sort is big-oh of the time taken by bubble-sort but not the other way. Justify your answer. (c) Show, with justification, that cocktail-shaker sort runs in O(n?) time. (d) Show, with justification, that cocktail-shaker sort runs in S2(n?) time. i.e., present an input of size n and show that on that input the algorithm does S2(n) work