Question

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 (i–1)

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, 1≤k≤n, 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, 1≤k≤n)

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]

Answer 1

Array after first iteration
[8 5 11 6 10 7 9 12]

Array after second iteration
[8 5 9 6 10 7 11 12]

Array after third iteration
[8 5 9 6 7 10 11 12]

Algo:

1. for i=0 to n-k+1
2.    position=i
3.    for j=1 to (i–1)
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
9. return A[n-k+1]