4.(18 points) Determine a Loop Invariant for the outer for loop of the Selection-Sort algorithm below that allows you to prove that the algorithm is correct. Then state the proof. Parts of both are given fill in the blanks. Understanding how this algorithm works will give you the needed information to construct an appropriate loop invariant.

Selection-Sort(A: Array [1..n] of integer)

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 positioni then

6 temp=A[i]

7 A[i]=A[position]

8 A[position]=temp

Explanatory Notes: The key here is to first understand how this algorithm sorts by finding the position of the largest number in the array A[1,n] and swapping that with the n^thcell of the array, then finding the position of the largest number in the array A[1,(n-1)] and swapping that with the (n-1)^thcell of the array, and repeating this process for subarrays A[1,(n-2)], A[1,(n-3)],,A[1,2]. Note that the outer loop is executed (n-1) times, with the value of the loop variable i going from n down to 2. So during the first execution of the outer loop (line 1), i=n, after which A[n] will contain the (first) largest number in the array and i will be decremented to n-1. During the second execution of the outer loop, i=n-1, after which A[n] will contain the first largest number in the array and A[n-1] will have the second largest number in the array and i will be decremented to n-2. During the third execution of the outer loop, i=n-2, after which A[n] will contain the first largest number in the array and A[n-1] will have the second largest number in the array, and A[n-2] will have the third largest number in the array and i will be decremented to n-3. During the k^thexecution of the outer loop (we are using k to count the loop executions because the loop variable i is decremented and so does not count the number of executions of the loop itself), i=n-k+1, after which A[n] will contain the first largest number in the array and A[n-1] will have the second largest number in the array, etc., and i will be decremented to n-k.

Loop Invariant:

Before k^thexecution of the outer loop (line 1), the loop variable i=n-k+1, and ___________________ largest numbers in array A will be in the subarray _______________.

Initialization:

The LI should hold before the first execution of the loop: Before the 1^stexecution of the loop, the loop variable i=n-1+1=n, and 0^th,,1^stlargest numbers in array A will be in subarray A[(n+1)n]. But both the 0^thlargest number and the subarray A[n+1n] are undefined for an array of n numbers. So the LI trivially holds.

Maintenance:

Here we have to show that if the LI held true before the k^thexecution of the loop, it must also be true after the k^thexecution, i.e., before the (k+1)^thexecution.

So suppose before the k^thexecution of the loop the LI holds, i.e., the loop variable i=n-k+1, and the ______________ largest numbers in array A are in the subarray _______________.

During this execution, the local variable position is initialized to i=n-k+1 (line 2).

The for loop executes for each value of j from 1 to (i-1)=(n-k) (line 3).

Each time, if a number A[j] greater than A[position] is found then position is updated to j. Therefore, since position starts out being (n-k+1) and j goes from 1 to (n-k), at the end of this loop, position will contain the index of the largest number in the subarray _______________.

Line 5 checks to see if this index is the same as i=(n-k+1). If it is, then nothing is done, and the largest number in subarray ___________ is in array cell __________. If it is not, then A[position] and A[n-k+1] are swapped by lines 6-8 so that the largest number in subarray ___________ is in array cell __________.

Since the ___________________largest numbers in array A were already in the subarray __________ before the k^thexecution of the loop started, this means that by the end of the k^thexecution of the loop, the k^thlargest number will be in array cell __________.

Finally, by the nature of the for loop, the loop variable i is decremented to n-k, and the k^thexecution of the loop finishes.

So after the k^thexecution of the loop finishes, i.e., before the (k+1)^thexecution of the loop, the loop variable i=______, and the ___________________ largest numbers in array A will be in the subarray ____________.

Thus, if the LI holds before the k^thexecution of the loop, it will hold before the (k+1)^thexecution of the loop.

Termination:

As we have proved initialization and maintenance, it holds that LI must be true after the loop finishes. The loop is executed (n-1) times. So after the (n-1)^thexecution, i.e., before the n^thexecution, the loop variable i=__________, and the _________________ largest numbers in array A will be in the subarray _____________. Since the first (n-1) largest numbers are thus now already sorted, what is in A[1] must be the n^thlargest, i.e., the smallest, number in the input array. Therefore A is fully sorted in the increasing order.