Correctness of bubblesort Bubblesort is a popular, but

Chapter 2, Problem 2-2

(choose chapter or problem)

Correctness of bubblesort Bubblesort is a popular, but inefficient, sorting algorithm. It works by repeatedly swapping adjacent elements that are out of order. BUBBLESORT.A/ 1 for i D 1 to A:length 1 2 for j D A:length downto i C 1 3 if Aj < Aj 1 4 exchange Aj with Aj 1 a. Let A0 denote the output of BUBBLESORT.A/. To prove that BUBBLESORT is correct, we need to prove that it terminates and that A0 1 A0 2 A0 n ; (2.3) where n D 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 24, 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 14 that will allow you to prove inequality (2.3). Your proof should use the structure of the loop invariant proof presented in this chapter. d. What is the worst-case running time of bubblesort? How does it compare to the running time of insertion sort?