public class InsertionSort
{

    /**
     * Constructor for objects of class InsertionSort
     */
    public static void InsertionSort()
    {
        int r[] = ArrayMaker.getArray(20);
        ShowArray.show(r);

        boolean finished = false;
        int i = 1;
        int j = 1;

        //inv1 : gesorteerd([0..i-1])

        while (i!= r.length)
        {
            //inv1 : gesorteerd([0..i-1])
            j=i;
            finished = false;

            //inv2: gesorteerd([0..j-1]) &&  gesorteerd([j..i])
            while (finished == false && j>0)
            {
                if (r[j] < r[j-1])
                {
                    //gesorteerd([0..j-1]) &&  gesorteerd([j..i]) && r[j] < r[j-1]
                    Wissel.wissel(r, j, j-1);
                    //gesorteerd([0..j-2]) && gesorteerd([j-1..i])
                    j--;
                    //gesorteerd([0..j-1]) && gesorteerd([j..i])
                }
                else
                {
                    // gesorteerd([0..j-1]) && gesorteerd([j..i])  && r[j] < r[j-1]
                    //=> gesorteerd[0..j]
                    finished = true;
                }
            }
            //2 mogelijkheden:
            //=> gesorteerd([0..j-1]) &&  gesorteerd([j..i]) && j = 0
            // of (else blok) => gesorteerd[0..j]
            // => algemeen: gesorteerd([0..i])
            i++;
            //=> gesorteerd([0..i-1)]
        }
        //gesorteerd([0..i-1]) && i = r.length
        //=> gesorteerd([0..lengte-1]
        ShowArray.show(r);
    }
}