2-2 Correctness of bubblesort

Bubblesort 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)
  for i = 1 to n - 1
      for j = n downto i + 1
          if A[j] < A[j-1]
              exchange A[j] with A[j-1]

a. Let $A'$ denote the array $A$ after BUBBLESORT> (A, n) is executed. To prove that it terminates and that $$ A'[1] \leq A'[2] \leq \cdots \leq A'[n] $$ In order to show that BUBBLESORT actually sorts, what else do you need to prove?

The next two parts prove inequality (2.5).

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-nvariant 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 1-4 that allows you to prove inequal ity (2.5). 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 with the running time of INSERTION-SORT?

a

$A'$ consist of all the elements of $A$

b

loop invariant: At the start of each iteration of $for$ loop in lines 2-4, $A[j:n]$ consist of the elements originally in $A[j:n]$ before entering the loop but possibly in a different order, and $A[j]$ is the smallest one of them.

Initialization: $j=n$, $A[n]$ consist of the elements originally in A$[n]$ and it is the smallest.

Maintenance: During the iteration, if$A[j-1]<A[j]$, we swap them. So A[j-1] will be the smallest and A[j-1:n] consist of the elements originally in $A[j-1:n]$. Decresementing j preserves the loop invariant.

Termination: the loop terminates when $j = i$, $A[i:n]$ consist of the elements originally in $A[i:n]$ before entering the loop but possibly in a different order, and $A[i]$ is the smallest one of them.

c

Loop invariant: At the start of each iteration of the for loop of lines 1-4, the subarray $A[1..i − 1]$ consists of the $i - 1$ smallest elements in $A[1..n]$ in sorted order. $A[i..n]$ consists of the $n - i + 1$ remaining elements in $A[1..n]$.

Initialization: Initially the subarray $A[1..i − 1]$ is empty and trivially this is the smallest element of the subarray.

Maintenance: From part (b), after the execution of the inner loop, $A[i]$ will be the smallest element of the subarray $A[i..n]$. And in the beginning of the outer loop, $A[1..i − 1]$ consists of elements that are smaller than the elements of $A[i..n]$, in sorted order. So, after the execution of the outer loop, subarray $A[1..i]$ will consists of elements that are smaller than the elements of $A[i + 1..n]$, in sorted order.

Termination: The loop terminates when $i = A.length$. At that point the array $A[1..n]$ will consists of all elements in sorted order.

d

The $i$th iteration of the for loop of lines 1-4 will cause $n − i$ iterations of the for loop of lines 2-4, each with constant time execution, so the worst-case running time of bubble sort is $\Theta(n^2)$ which is same as the worst-case running time of insertion sort.