C++

Forum

 
Loop Invariant

gingertouch (5)
So here's the dealio I had a question on my most recent exam dealing with the concept of loop invariant in a function, and I am wondering if the solution provided is something known among the community.

Question
In the implementation of Selection Sort below, insert the loop invarian that accurately describes the sorting of the array in the proper four places. The invariant may either be in the form of a comment or an assertion.

1
2
3
4
5
6
7
8
9
10
11
12
13
 
void SelectionSort(int A[], int numberOfItems)
{
    int minIndex;

    for (int i = 0; i < numberOfItems - 1; i++)
    {
         
         minIndex = FindMinimal(A, i, numberOfItems);
         Swap(A, i, minIndex);
         
    }

}

now the places where the invariant was supposed to be placed were the 4 blank lines, this is how the solution looked. 

1
2
3
4
5
6
7
8
9
10
11
12
13
 
void SelectionSort(int A[], int numberOfItems)
{
    int minIndex;
    //A[0..i-1] is ordered
    for (int i = 0; i < numberOfItems - 1; i++)
    {
         //A[0..i-1] is ordered
         minIndex = FindMinimal(A, i, numberOfItems);
         Swap(A, i, minIndex);
         //A[0..i-1] is ordered
    }
    //A[0..i-1] is ordered
}

(first, why isnt it [0..i] instead of [0..i-1])
I understand that it works for the part inside the for loop, but for the parts before and after i is not able to be used, therefore eliminating the ability to use assertion.

The exact question i'm looking to get answered is whether or not it is a known thing that when thinking about the invariant outside of the loop it is okay to use i?
PS I have found 1 source that also does this, but no where else, im skeptical.
http://firner.com/weblog/article/selection-sort

Thanks,
Ginger
Last edited on
Peter87 (11178)
It doesn't make sense to use i outside the loop. The array doesn't have to be sorted before you pass it to the function so line 4 doesn't make sense. Line 12 they should have used numberOfItems instead of i.
//A[0..numberOfItems-1] is ordered

Line 7 looks correct.

Line 10 position i is now also in the sorted sequence so it should be
//A[0..i] is ordered
gingertouch (5)
So since my teacher wanted all four to be the exact same, than there really is no way to write them as he wanted, unless it is acceptable to use i outside of the loop when speaking of the invariant, from what I gather though it is not.
Even if it was acceptable, to have the invariant the exact same in all four spots and to be true it would have to be /ordered A[0]...A[i]/, where i would start at 0 and end at numberOfItems-1.

thanks a ton.
Last edited on
Catfish3 (666)
Last edited on
gingertouch (5)
yes but then arises another problem, first minIndex isn't initialized, and still the problem of i being used outside of the loop exists, unless you were ignoring that one.

Edit: well now why'd you delete your comment, now mine makes no sense :P
also i'm on a school computer and cant update my java, and its not running. :(
Last edited on
Catfish3 (666)
I removed my invariant suggestion because it seemed stupid, before I saw your reply.

I think it was A[i] <= A[minIndex].

yes but then arises another problem, first minIndex isn't initialized, and still the problem of i being used outside of the loop exists, unless you were ignoring that one.

I know, but those artificial issues can be dealt with by rewriting the for() loop as a while(), just as on that Java website.
gingertouch (5)
ahh thats what it is showing, or i believe that you could keep the for loop and just write it like this, with the altered invariant of [0...i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
void SelectionSort(int A[], int numberOfItems)
{
    int minIndex;
    int i = 0
    //A[0..i] is ordered
    for (i = 0; i < numberOfItems - 1; i++)
    {
         //A[0..i] is ordered
         minIndex = FindMinimal(A, i, numberOfItems);
         Swap(A, i, minIndex);
         //A[0..i] is ordered
    }
    //A[0..i] is ordered
}


although i understand you can change it to make it work, we were not to change the code, just develop the same invariant for all 4 spots.
Catfish3 (666)
this is how the solution looked.

... followed by a code snippet that has
A[0..i-1] is ordered
invariants. If that's the solution given by your teacher, ignoring that i isn't in scope, I think your invariant is good too.

It also makes more sense because for i == 0 you'd have
A[0 .. -1] is ordered
for the original invariant.
Or maybe I misunderstood your first post?
Last edited on
gingertouch (5)
No, that's pretty much what i was asking about,
thanks!
Topic archived. No new replies allowed.