Correctness and the Loop Invariant

  • + 2 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.

    using System;
    using System.Collections.Generic;
    using System.IO;
    using System.Linq;
    
    class Solution { 
        private static bool isSorted (int[] pArray, int pIndex) {
            if (pIndex == 0) {return true;}
            bool sorted = true; 
            for (int i=0; i<pIndex&&sorted;i++) {
                if (pArray[i] > pArray[i+1]) {
                    sorted = false; 
                }
            }
            return sorted; 
            
        }
        public static void insertionSort (int[] A) { 
            var j = 0; 
            for (var i = 1; i < A.Length; i++) { 
                var value = 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)); 
        }
    
        static void Main(string[] args) { 
            Console.ReadLine(); 
            int [] _ar = (from s in Console.ReadLine().Split() select Convert.ToInt32(s)).ToArray();
            insertionSort(_ar); 
        }
    }