1. (Algorithms and limits) (a) Consider the following algorithm to sort a list. Input: a list L= (L1,L2,...In) of n numbers, where all of them are different. Output: the list L ordered from smallest to greatest. Algorithm. 1) Set swapcount to 0. 2) One by one, starting with the first entry in our list and working our way through our entire list L, compare two consecutive elements lk and lk+1. a) If lk > lk+1 then swap these elements and increase swapcount by 1. b) Go to the next pair lk+1 and lk+2. 3) If swapcount is not 0 then go to 1). 4) Otherwise stop. We have sorted the list. Prove that the output of the algorithm above is indeed the sorted version of L (from smallest to greatest). (b) Find the worst running time of the algorithm above. An elementary operation is a data move or a comparison. Note that a swap is considered to be just 2 elementary operations. You can ignore addition in the update of swapcount on Step 2), that is, updating swapcount is only one elementary operation (write). Explain your