Bubble Sort!

Concept summary and lesson

Sorting is a major piece of computer science algorithm design. It's an incredibly versatile thing, and it's also not as easy as you'd think to get it done quickly. We're going to learn the simplest sorting algorithm I know today, and talk about how slow it is. It's called Bubble Sort.

It gets its name from the way the elements move through the list while you're sorting it (the biggest elements tend to bubble to the end of the list).

All sorting algorithms have a few things in common:

Here's the basic idea:

  1. Start at the first element of the list, and look at the ordering of it and the next one.
  2. If they're in the right order, move on to the next element.
  3. If they're in the wrong order, swap them!
  4. Now move to the next element of the list (don't skip any, even if it's the one you just swapped!)
  5. Go to step 2 and repeat until you reach the end of the list
  6. Go to step 1 and repeat, but stop one element farther from the end for each iteration until there are only two unsorted elements left, then sort them!

The algorithm will pick up the biggest element it has seen up until each point and carry it along until it either reaches the end of the unsorted items, or it reaches the end of the list. In either case, it drops the biggest item and starts over.

Examples/demo

Bubble Sort animation

Media resources

Exercises