Algorithms and Their Analysis:

Question 3 (1.5 credit) Bubble sort is a popular, but inefficient, sorting algorithm. It works by repeatedly swapping adjacent elements that out of order. BUBBLESORT(A) 1. fori - 1 to A.length -1 2. forj i1 to A.length 3. 4. exchange AU with Al] a) A loop invariant for the outer for loop in lines 1-4 is: At iteration i, the sub-array A[ 1i] is sorted and any element in A[i+1..Asize is greater or equal to any element n A[1.i Prove that this loop invariant holds using the structure of proof presented on slides 7-9 and 27-28 from lecture 2 b) What is the worst-case running time of bubblesort? How does it compare to the running time of insertion sort