Consider the following algorithm that sorts an array of distinct integers: (it starts on the left and bubblesorts to the right )(putting the largest number on the right). Then it starts from the right and reverse bubble sorts to the left (putting the smallest number on the left.) Then zigzagging back and forth until the list is sorted.

Zigzag BubbleSort( 21,..., An, array of distinct integers) 1. i=1 2. j=n 3. while i Ak+1: 6. swap ak and ak+1 7. j=j-1 8. for k from , down to i+ 1 j 9. if ak 1, how many comparisons of lis tries (lines 5 bleSort make in the worst case? (Show your work.) 9) does ZigzagBub- 1 (c) For a list of length n > 1, how many swaps of list entries does ZigzagBubbleSort make in the worst case? Give a general example for an arbitrary n that achieves the maximum number of swaps. (Show your work.) (d) How could you edit the pseudocode of ZigzagBubblesort so that it exits early