BUBBLESORT (A) 1 for i 1 to A. length-1 for j = A, length downto i + 1 4 exchange Ai] with Ai -1 a. Let A' denote the output of BUBBLESORT(A). To prove that BUBBLESORT is correct, we need to prove that it terminates and that (2.3) where n- A.length. In order to show that BUBBLESORT actually sorts, what else do we need to prove? The next two parts will prove inequality (2.3). b. State precisely a loop invariant for the for loop in lines 2-4, and prove that this loop invariant holds. Your proof should use the structure of the loop invariant proof presented in this chapter. c. Using the termination condition of the loop invariant proved in part (b), state a loop invariant for the for loop in lines 1-4 that will allow you to prove n equality (2.3). Your proof should use the structure of the loop invariant proof resented in this chapter. BUBBLESORT (A) 1 for i 1 to A. length-1 for j = A, length downto i + 1 4 exchange Ai] with Ai -1 a. Let A' denote the output of BUBBLESORT(A). To prove that BUBBLESORT is correct, we need to prove that it terminates and that (2.3) where n- A.length. In order to show that BUBBLESORT actually sorts, what else do we need to prove? The next two parts will prove inequality (2.3). b. State precisely a loop invariant for the for loop in lines 2-4, and prove that this loop invariant holds. Your proof should use the structure of the loop invariant proof presented in this chapter. c. Using the termination condition of the loop invariant proved in part (b), state a loop invariant for the for loop in lines 1-4 that will allow you to prove n equality (2.3). Your proof should use the structure of the loop invariant proof resented in this chapter