Question 1. (1 marks) Consider the sorting algorithm given by the pseudocode bel

Question

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 answer.

Explanation / Answer

a) At the ith iteration:

   Array upto i-1 is sorted.
   A[i] has to be inserted in that
   So the maximum number of possible swaps will be i-1 in the
   worst case. So
   Si = i-1;

b) Maximum expected value of total number of swaps will be (in the worst case):
    s2 + s3 + s4 +....+sn = 1 +2 + 3 + ....+ n-1 = n * (n-1)/2

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.