2. (Adapted from Exercise 2.2-2 in the textbook) Below is pseudocode for selecti
ID: 3746030 • Letter: 2
Question
2. (Adapted from Exercise 2.2-2 in the textbook) Below is pseudocode for selection sort, which works by finding the minimum element of A, and storing it in A[1], then finding the second smallest element of A, and storing it in A[2], and so on. SELECTION-SORT (A) 1 fori-1 to A.length-1 for j = i+1 to A. length 4 exchange A[i] with Aj] State precisely a loop invariant for the inner for loop in lines 2-4, and prove that this loop invariant holds. Your proof should resemble the structure of the loop invariant proofs in Sections 2.1 and 2.3 of the textbook, including arguments for Initialization, Maintenance, and Termination. a. b. Using your answer from part a, state precisely a loop invariant for the outer for loop in lines 1-4, and prove that this loop invariant holds. c. To prove that Selection-Sort is correct, we must prove that the fial ii a permutation (reordering) of the original list A such that A[1] S A121 s... S A'In]. Your answer from part b should prove that A[1] s AT2] S S A'[n], so explain why we know that the final list A' is a permutation (reordering) of the original list A. Give a best-case and worst-case running time for selection sort using O-notation and argue informally that your answer is correct. d.Explanation / Answer
Please note that as per Chegg Policy, we are only supposed to do only the first question in a set of questions. I am doing the first question in an elaborated way and done the rest as much as I can do. Please upvote my answer.
Loop Invariant:
Before the start of each loop, A[min] is less than or equal to A[i..j-1].
Initialization:
Prior to the first iteration of the loop, j=i+1. So the array segment A[i..j-1] is really just spot A[i]. Since line 2 of the code sets min = i, we have that min indexes the smallest element (the only element) in subarray A[i..j-1] and hence the loop invariant is true.
Maintenance:
Before pass j, we assume that min indexes the smallest element in the subarray A[i..j-1]. During iteration j we have two cases: either A[j] < A[min] or A[j] A[min]. In the second case, the if statement on line 4 is not true, so nothing is executed. But now min indexes the smallest element of A[i..j]. In the first case, line 5 switches min to index location j since it is the smallest. If min indexes an element less than or equal to subarray A[i..j-1] and now A[j] < A[min], then it must be the case that A[j] is less than or equal to elements in subarray A[i..j-1]. Line 5 switches min to index this new location and hence after the loop iteration finishes, min indexes the smallest element in subarray A[i..j].
Termination:
At termination of the inner loop, min indexes an element less than or equal to all elements in subarray A[i..n] since j = n+1 upon termination. This finds the smallest element in this subarray and is useful to us in the outer loop because we can move that next smallest item into the correct location.
b. Loop Invariant:
In the outer loop, array is sorted for first i elements. i.e.,
d. Time Complexity:-
For each iteration i, the inner loop runs from i to n, and does constant amount of work for each j value. Hence, the inner loop takes time O(n i), which is O(n). So the total amount of work is
En1i=1 O(n)
= O( En1i=1 n)
= O((n 1)n)
= O(n2 ).
Can the algorithm really take time n2 ? Let us look for a lower bound on its performance. In fact, notice that for any array, the algorithm will run the inner loop from i to n (even if the array were already sorted), so the running time of the i th iterations is (n i). So the total running time is
=En1i=1 (n i)
=(En1i=1 n i)
=(En1i=1 i)
= (n(n 1)/2)
= (n2 )
(In the middle step here, we noticed that the sum Pn1 i=1 ni is equal to (n1)+(n2)+...+3+2+1. That is the same as 1 + 2 + 3 + ... + (n 2) + (n 1), just in opposite order. So we were allowed to replace the sum by En1i=1 i.) So our analysis is actually tight up to constants: the algorithm in the worst case takes exactly (n2 ) steps
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.