Discussion on Correctness and the Loop Invariant Challenge

4 years ago+ 1 comment

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); 
    }
}