Answer

Prove that the basic Bubblesort algorithm is correct. (Grossman, pg. 349)

(1) The Proposition

"After the ith pass through the outer loop of BUBBLESORT, the list still contains the original numbers and the largest i numbers are correctly placed in the last i locations in the array."

(2) The Base Case

After the 1st pass, the largest number is in the 1st location in the array.

(3) The Inductive Hypothesis

"After the (i - 1)th pass, the list still contains the same numbers and the largest (i - 1) numbers are correctly placed in the last (i - 1) locations in the list."

(4) The Inductive Step = Show the statement in (3) to be true for the ith pass.

a. Since the inner loop does not touch any number in the list beyond the (n - i + 1)th number, the largest (i - 1) numbers remain in their correct postions.
b. The overall list is unaltered in the loop because BUBBLESORT just switches pairs of numbers.
c. You can show the ith largest number in the list in A[1. . .(n - i + 1)] numbers ends up as the (n - i + 1)th number after the ith pass is completed. During this pass, j = 1, 2,..., (n-1). In the jth pass, the largest number in A[1. . .(j + 1)] is forced to be A[j + 1] by the if...then statement. And by the Inductive Hypothesis, all the other numbers are already where they're supposed to be. Therefore after the ith pass, A[n - i + 1] does contain the ith largest number in the list.

(5) Therefore the BUBBLESORT algorithm is correct.

Back to:

Top of Page | Table of Contents | Glossary