Consider the sorting algorithm given by the pseudocode below. It takes an array A[1..n] of size...

 

Transcribed Image Text:

Consider the sorting algorithm given by the pseudocode below. It takes an array A[1..n] of size n, and outputs A with its elements in sorted (non-decreasing) order. 1 for i = 2 to n 2 j=i-1 234 NO 5 while A[j+1]< A[j] & j≥1 swap A and A[j+1] j=j-1 In the following subquestions, assume that the array A contains a uniformly chosen random permuta- tions of the integers 1,...,n. a. Let S; 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₁+...+ S-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 answer. Consider the sorting algorithm given by the pseudocode below. It takes an array A[1..n] of size n, and outputs A with its elements in sorted (non-decreasing) order. 1 for i = 2 to n 2 j=i-1 234 NO 5 while A[j+1]< A[j] & j≥1 swap A and A[j+1] j=j-1 In the following subquestions, assume that the array A contains a uniformly chosen random permuta- tions of the integers 1,...,n. a. Let S; 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₁+...+ S-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 answer.

Answer rating: 100% (QA)

a To find the expected value of the number of swaps S in the ith iteration of the forloop we need to ... View the full answer