Overview

"Bubble up" the largest item to the end, then the next largest, and so on.

Algorithm

For each iteration:

• Compare the first and second. If they are out of order, swap them.
• Compare the second and third. If they are out of order, swap them.
• Continue until the last two are compared and swapped if necessary.

1. Iteration #1: Consider all n items. When you're done, the largest will be in its final position; it no longer needs to be considered for swapping.
2. Iteration #2: Consider the first (n-1) items. When done, the second largest will be in its final position.
3. Continue to iterate until the number of items being considered is just 1. You're done!

Exercise

In the table below, show what the data looks like after each iteration of the algorithm.

2	4	5	3	1

What is the Loop Invariant for Bubble Sort?

A "loop invariant" is a true statement you can make about the data at each step. It does not describe how the algorithm works.
Complete this sentence: "At the ith step of the bubblesort algorithm ... "