@@ -0,0 +1,2297 @@
+package algorithms.sorting;%0D%0A%0D%0Aimport java.util.*;%0D%0A%0D%0A/*%0D%0A * Problem Statement: %0D%0A * In the previous challenge, you wrote code to perform an Insertion Sort on an%0D%0A * unsorted array. But how would you prove that the code is correct? I.e. how do%0D%0A * you show that for any input your code will provide the right output?%0D%0A * %0D%0A * Loop Invariant:%0D%0A * In computer science, you could prove it formally with a loop invariant, where%0D%0A * you state that a desired property is maintained in your loop. Such a proof is%0D%0A * broken down into the following parts:%0D%0A * %0D%0A * Initialization: It is true (in a limited sense) before the loop runs.%0D%0A * Maintenance: If it's true before an iteration of a loop, it remains true%0D%0A * before the next iteration.%0D%0A * Termination: It will terminate in a useful way once it is finished.%0D%0A * %0D%0A * Challenge: %0D%0A * In the InsertionSort code below, there is an error. Can you fix it? Print the%0D%0A * array only once, when it is fully sorted.%0D%0A * %0D%0A * Details:%0D%0A * The Input format and the constraints are the same as in the previous%0D%0A * challenges and are presented below.%0D%0A * %0D%0A * Input Format:%0D%0A * There will be two lines of input:%0D%0A * %0D%0A * s - the size of the array%0D%0A * ar - the list of numbers that makes up the array%0D%0A * %0D%0A * Output Format:%0D%0A * Output the numbers in order, space-separated.%0D%0A * %0D%0A * Constraints:%0D%0A * 1 %3C= s %3C= 1000%0D%0A * -1500 %3C= V %3C= 1500,V is an element of ar%0D%0A * %0D%0A * Sample Input: %0D%0A * 6%0D%0A * 1 4 3 5 6 2%0D%0A * %0D%0A * Sample Output: %0D%0A * 1 2 3 4 5 6%0D%0A */%0D%0Apublic class CorrectnessAndTheLoopInvariant %7B%0D%0A%0D%0A    public static void insertionSort(int%5B%5D A)%7B%0D%0A        for(int i = 1; i %3C A.length; i++)%7B%0D%0A            int value = A%5Bi%5D;%0D%0A            int j = i - 1;%0D%0A            while(j %3E= 0 && A%5Bj%5D %3E value)%7B%0D%0A                A%5Bj + 1%5D = A%5Bj%5D;%0D%0A                j = j - 1;%0D%0A            %7D%0D%0A            A%5Bj + 1%5D = value;%0D%0A        %7D%0D%0A%0D%0A        printArray(A);%0D%0A    %7D%0D%0A%0D%0A%0D%0A    static void printArray(int%5B%5D ar) %7B%0D%0A        for(int n: ar)%7B%0D%0A            System.out.print(n+%22 %22);%0D%0A        %7D%0D%0A    %7D%0D%0A    public static void main(String%5B%5D args) %7B%0D%0A        Scanner in = new Scanner(System.in);%0D%0A        int n = in.nextInt();%0D%0A        int%5B%5D ar = new int%5Bn%5D;%0D%0A        for(int i=0;i%3Cn;i++)%7B%0D%0A            ar%5Bi%5D=in.nextInt();%0D%0A        %7D%0D%0A        insertionSort(ar);%0D%0A        in.close();%0D%0A    %7D%0D%0A%7D

Add CorrectnessAndTheLoopInvariant