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

BUBBLESORT(A)

1. for i = 1 to A.length 1

2. for j = i + 1 to A.length

3. if A[j] < A[i]

4. exchange A[j] with A[i]

a) A loop invariant for the outer for loop in lines 1 4 is: At iteration i, the sub-array A[1..i] is sorted and any element in A[i+1..A.size] is greater or equal to any element in 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?

From slides

INSERTION-SORT(A)

1. for j = 2 to A.length

2. key = A[j]

3. // Insert A[j] into the sorted sequence A[1 .. j-1]

4. i = j 1

5. while i > 0 and A[i] > key

6. A[i + 1] = A[i]

7. i = i 1

8. A[i + 1] = key

INSERTION-SORT(A)

1. for j = 2 to A.length

2. key = A[j]

3. // Insert A[j] into the sorted sequence A[1 .. j-1]

4. i = j 1

5. while i > 0 and A[i] > key

6. A[i + 1] = A[i]

7. i = i 1

8. A[i + 1] = key