Question 1. (1 marks) Consider the sorting algorithm given by the pseudocode below. It takes an array A1..n] of size n, and outputs A with its elements in sorted (non-decreasing) order. l fori 2 to n 2 ji 1 swap Aj) and Alj 1] j=j-1 In the following subquestions, assume that the array A contains a uniformly chosen random permuta- tions of the integers l, n. a. Let Si be the number of swaps performed by the algorithm in the i-th iteration of the for-loop. What is the exact expected value of S as a function of n and i? Justify your answer. b. Let S-S+Sn-1 be the total number of swaps performed by the algorithm. What is exact expected value of S as a function of n? Justify your