We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Reading the discussion here, I think we're missing a very important point:
The issue is not to simply solve the problem with the algorithm and pass the test cases. The purpose of the exercise is
1) To write a loop invariant test as an addition to the loop.
2) Use this loop invariant to diagnose the problems at an early a stage as possible.
3) Correct the problem.
If we miss out on stage 1 and 2 by simply changing < to <=, we're missing the point of the exercise. We may get all the points for passing the test cases, but we're no better prepared to actually use an invariant in a loop where the problem is not as trivial.
Here's my crack at the solution. It gives no more points than anyone else's, but I did build a loop invariant into the system which will then print out an error message in the event of a failure, allowing the user to know exactly when things started going wrong and the state of the system at that time.
usingSystem;usingSystem.Collections.Generic;usingSystem.IO;usingSystem.Linq;classSolution{privatestaticboolisSorted(int[]pArray,intpIndex){if(pIndex==0){returntrue;}boolsorted=true;for(inti=0;i<pIndex&&sorted;i++){if(pArray[i]>pArray[i+1]){sorted=false;}}returnsorted;}publicstaticvoidinsertionSort(int[]A){varj=0;for(vari=1;i<A.Length;i++){varvalue=A[i];j=i-1;while(j>=0&&value<A[j]){A[j+1]=A[j];j=j-1;}A[j+1]=value;if(!Solution.isSorted(A,i-1)){Console.WriteLine("Sort Failed at index: "+(i-1)+" string: '{0}",string.Join(", ",A.Select(v=>v.ToString()))+"'");}}Console.WriteLine(string.Join(" ",A));}staticvoidMain(string[]args){Console.ReadLine();int[]_ar=(fromsinConsole.ReadLine().Split()selectConvert.ToInt32(s)).ToArray();insertionSort(_ar);}}
Correctness and the Loop Invariant
You are viewing a single comment's thread. Return to all comments →
Reading the discussion here, I think we're missing a very important point:
The issue is not to simply solve the problem with the algorithm and pass the test cases. The purpose of the exercise is 1) To write a loop invariant test as an addition to the loop.
2) Use this loop invariant to diagnose the problems at an early a stage as possible.
3) Correct the problem.
If we miss out on stage 1 and 2 by simply changing < to <=, we're missing the point of the exercise. We may get all the points for passing the test cases, but we're no better prepared to actually use an invariant in a loop where the problem is not as trivial.
Here's my crack at the solution. It gives no more points than anyone else's, but I did build a loop invariant into the system which will then print out an error message in the event of a failure, allowing the user to know exactly when things started going wrong and the state of the system at that time.