Bubblesort is a popular, but inefficient, sorting algorithm. It works by repeatedly swapping adjacent elements that are out of order.

BUBBLESORT(A) for i = 1 to A:length - 1 for j = A.length downto i + 1 if A(j) < A(j-1) exchange A(j) with A(j-1)

1. Show correctness by inserting invariant and assert statements. There are two loops insert invariant and assert statement at the correct places in the algorithm 2. Show complexity by counting the number of exchanges in the worst case. Derive the method for calculating the number of iterations and then find the number of actual swaps.