10. Understanding and modifying algorithms: Selection problem (12 points)

First, understand the Selection-sort algorithm below:

Selection-sort(A: Array [1..n] of numbers)

1 for i=n down to 2

2 position=i

3 for j=1 to (i1)

4 if A[j]>A[position] then position=j

5 if position i then

6 temp=A[i]

7 A[i]=A[position]

8 A[position]=temp

(4 points) If input A=[12,5,11,6,10,7,9,8], what will A be after the 3^rd iteration of the outermost for loop of the Selection-sort algorithm completes? A=[__, __, __, __, __, __, __, __]

(8 points) Modify the algorithm to solve the problem of finding the k-th largest number in array A, 1kn, without sorting the entire array. Parts of the algorithm are given below. Fill in the blanks.

Select-k-th-largest(A: Array [1..n] of numbers; k: integer, 1kn)

1 for _____________________

2 ________________

3 for _____________________

4 if _______________ then ___________

5 if position i then

6 temp=A[i]

7 A[i]=A[position]

8 A[position]=temp

9 return A[n-k+1]