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

Answer 1(a):

According to algorithm we are moving any paticular element owards the front of array in order to sort the array in ascending order. So in any i'th iteration number of swaps Si will be equal to i i.e; Si = i where i => [ 1,2,3.. n-1 ]

---------------------------------------------------------------------

Answer 1(b):

Values of number of swaps will be,

S1 = 1

S2 = 2

S3 = 3

......

......

Sn-1 = n-1

Now, taking summation

S = 1 + 2+ 3 + ...... + (n-1)

We know sum of all numbers from 1 to n is equal to n(n-1)/2 and here n = n-1.

S = (n-1)(n-2)/2

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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