**Correctness of bubble sort**

Bubble sort is a popular but inefficient sorting algorithm. It works by repeatedly swapping adjacent elements that are out of order. The procedure BUBBLESORT sorts array A[1:n]

BUBBLESORT(A, n)
1

**for**i = 1 to n - 1 2**for**j = n**downto**i + 1 3**if**A[j] < A[j-1] 4 exchange A[j] with A[j-1]- Let denotes the array A after BUBBLESORT(A, n) is executed. To prove that BUBBLESORT is correct, you need to prove that it terminates and that
………………
**(2.5)**In order to show that**BUBBLESORT**actually sorts, what else do you need to prove?

- 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.

- 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 allows you to prove inequality (2.5). Your proof should use the structure of the loop-invariant proof presented in this chapter.

- What is the worst-case running time of BUBBLESORT? How does it compare with the running time of INSERTION-SORT?