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 = 1 to A.length - 1

2     for j = A.length downto i + 1

3          if A[j] < A[j-1]

4              exchange A[j] with A[j-1]

a. Let \(A'\) denote the output of BUBBLESORT(A). To prove that BUBBLESORT is correct, we need to prove that it terminates and that

\(A'[1] \leq A'[2] \leq \cdots \leq A'[n]\),

where \(n = A.length\). In order to show that BUBBLESORT actually sorts, what else do we need to prove?

We must prove that \(A'\) is comprised of the same elements from our input \(A\).

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

At the start of each iteration of the for loop of lines 2-4, the subarray \(A[j..n]\) consists of the elements originally in \(A[j..n]\), but in a different order such that \(A[j]\) is the smallest value.

Initialization: Before the first loop iteration, \(A[j..n] = A[n]\) which is in fact the original element in \(A[n]\). \(A[n]\) is trivially the smallest value since it is a single-valued array.

Maintenance: The body of the for loop works by comparing \(A[j]\) and \(A[j-1]\). \(A[j-1]\) is then made to be the smallest value of the two compared values, and then our array is expanded by 1 value on the left side. This new value(\(A[j-1]\)) is guaranteed to be the smallest value of the array, therefore decrementing \(j\) for the next iteration of the for loop preserves the loop invariant.

Termination: The loop terminates once \(j = i\). At this point, we have compared all values of \(A[i, n]\) so then \(A[i]\) is the smallest value among them and \(A[i..n]\) consists of all elements originally in \(A[i..n]\) before starting the loop.

c. 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 will allow you to prove the above inequality. Your proof should use the structure of the loop invariant proof presented in this chapter.

At the start of each iteration of the for loop of lines 1-4, the subarray \(A[1..i-1]\) consists of the smallest \(i-1\) elements originally in \(A[1..n]\), but in sorted order. \(A[i..n]\) contains the remaining \(n - i + 1\) largest elements of \(A\).

Initialization: Before the first loop iteration, \(A[1..i-1]\) is empty and therefore \(A[i..n]\) contains all elements originally in \(A\), which are all (trivially) greater than our empty array.

Maintenance: Our for loop on lines 2-4 executes once, ultimately resulting in the smallest element of \(A\) shifting into position \(A[i]\). \(A[1..i-1]\) is now one element larger, with the smallest element of \(A[i..n]\) in position \(A[i]\). After the execution of this loop, \(A[1..i]\) consists of all elements smaller than our remainder array \(A[i+1..n]\) in sorted order.

Termination: The loop terminates when \(i = n\) at which point the array \(A[1..n]\) consists of all elements originally in \(A\) in sorted order.

d. What is the worst-case running time of bubblesort? How does it compare to the running time of insertion sort?

The combination of both for loops is effectively an arithmetic series: \(\sum\limits_{k=2}^{n}k\) which results in a worst-case running time of \(\Theta (n^2)\), the same as INSERTION-SORT. Due to the structure of BUBBLE-SORT, the best-case running time is also \(\Theta (n^2)\) since we always perform the same number of comparisons. This sets it apart from INSERTION-SORT which has a \(\Theta (n)\) best-case running time.