I was wondering if someone could please help me with this problem. It's a bit complicated, and I'm utterly confused as to how to solve it. Please if you can explain with steps. Thank you!

BUBBLE SORT

Let A' (an array) denote the output of BubbleSort. In order to prove that BubbleSort is correct, we need to show that: 1. A' is a permutation of A; that is, A' has the same elements as A. 2. A'[1] A'[2] A'[3] ... A'[n-1] A'[n] The first part can be proven by showing that BubbleSort never removes or adds items to the array: it merely swaps them in line 4. For this, you will use loop invariants to prove the second part, i.e. that the resulting array is in order.

1) State precisely the 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 Chapter 2 of CLRS.

2) Using the termination condition of the loop invariant proved in part (a), state the loop invariant for the for loop in lines 1-4 that will allow you to prove the following inequality:

A'[1] A'[2] A'[3] ... A'[n-1] A'[n]

3) Give the worst-caserunning time of BubbleSort, in big-O notation, with justification. Give the best-caserunning time of BubbleSort, in big-O notation, with justification. How do these compare to the running time of InsertionSort?

BUBBLESORT(A) l fori to A.length 1 for j = A. length downto i + 1 exchange ALjl with AU