Bubble Sort

Bubble Sort takes in a list of values and sorts them from lowest to highest. It does this in two steps:

1. loop through each position from left to right. Per position:
   if the value at the current one is greater than the next, swap the values.
2. If at least one swap occurred during step one repeat the entire procedure, otherwise the list is sorted.

• Learn the basics of big-O notation
• Determine why bubble sort uses O(n²) or quadratic time in the worst case
• Determine why bubble sort uses O(1) or constant extra memory in any case, i.e. it works in-place.
• Briefly discuss applications.

• Hear the quick bubble sort song:
  1. The first part covers big-O analysis facts and a general description of the algorithm.
  2. The second covers the pseudocode which will help you program bubble sort in any programming language.
• Watch me demonstrate how to use the song lyrics to implement the algorithm in Python, the most straightforward programming language (in my opinion).