10. Understanding and modifying algorithms: Selection problem (12 points) First,
ID: 3747754 • Letter: 1
Question
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 (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 3rd 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]
Explanation / Answer
1) first iteration 8 5 11 6 10 7 9 12
second iteration 8 5 9 6 10 7 11 12
third iteration 8 5 9 6 7 10 11 12
2)
1 for i=n down 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]
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.