"Bubble up" the largest item to the end, then the next largest, and so on.
Algorithm
For each iteration:
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.
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 ... "