Resources‎ > ‎

## 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 ... "