Determine a Loop Invariant for the outer for loop of the Selection-Sort algorith

Question

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

                 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 nth cell 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)th cell 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 kth execution 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 kth execution 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 1st execution of the loop, the loop variable i=n-1+1=n, and 0th,…,1st largest numbers in array A will be in subarray A[(n+1)…n]. But both the 0th largest number and the subarray A[n+1…n] 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 kth execution of the loop, it must also be true after the kth execution, i.e., before the (k+1)th execution.

So suppose before the kth execution 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 kth execution of the loop started, this means that by the end of the kth execution of the loop, the kth largest 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 kth execution of the loop finishes.

So after the kth execution of the loop finishes, i.e., before the (k+1)th execution 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 kth execution of the loop, it will hold before the (k+1)th execution 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)th execution, i.e., before the nth execution, 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 nth largest, i.e., the smallest, number in the input array. Therefore A is fully sorted in the increasing order.

Explanation / Answer

Loop Invariant:

Before kth execution of the outer loop (line 1), the loop variable i=n-k+1, and __Kth__ largest numbers in array A will be in the subarray __A[1....(n-k)]__.

Initialization:

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

There is no meaning of 0th largest element, because if a element doesn't exist so there is no place to put the element. If there is no element then no sorting will take place.

Maintenance:

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

So suppose before the kth execution of the loop the LI holds, i.e., the loop variable i=n-k+1, and the ______kth________ largest numbers in array A are in the subarray _____A[1...(n-k)]______.

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 ______A[1....(n-k)]______.

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 __A[1....(n-k+1)]__ is in array cell __A[n-k+1]__. 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 __A[n-k+1....n]__ is in array cell __A[Position]__.

Since the ___k____largest numbers in array A were already in the subarray __A[(n-k+1).....n]__ before the kth execution of the loop started, this means that by the end of the kth execution of the loop, the kth largest number will be in array cell __A[n-k+1]__.

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

So after the kth execution of the loop finishes, i.e., before the (k+1)th execution of the loop, the loop variable i=__n-k+2__, and the __A[n-k+2]__ largest numbers in array A will be in the subarray __A[1....(n-k+2)]__.

Thus, if the LI holds before the kth execution of the loop, it will hold before the (k+1)th execution 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)th execution, i.e., before the nth execution, the loop variable i=___2___, and the ______A[2]___________ largest numbers in array A will be in the subarray ____A[1,2]_________. Since the first (n-1) largest numbers are thus now already sorted, what is in A[1] must be the nth largest, i.e., the smallest, number in the input array. Therefore A is fully sorted in the increasing order.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.