Question 1. (1 marks) Consider the sorting algorithm given by the pseudocode below. It takes an array Al1..n of size n, and outputs A with its elements in sorted (non-decreasing) order. 1 for 2 to n swap AL] and Alj +1] j-j-1 In the following subquestions, assume that the array A contains a uniformly chosen random permuta tions of the integers1,.. 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 Si as a function of n and i? Justify your answer b. Let S = S1 + + Sn-1 be the total number of swaps performed by the algorithm. What is ezaet expected value of S as a function of n? Justify your