Question

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

Answer 1

Here are your answers:

a)  Loop invariant: 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] before entering the loop but possibly in a different order and the first element A[j] is the smallest among them.

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

b) The ith 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 Θ(n^2) which is same as the worst-case running time of insertion sort.

However, insertion sort has best-case running time of Θ(n) which is faster than the best-case running time Θ(n^2) of bubble sort.

Thanks!