What Is Bubble Sort and How Does It Work?

Bubble Sort is an easy way to sort (or arrange) items in a list. Usually, we want to put them in order from smallest to largest.

Key Features:

• Type of Sorting: It compares items.
• Time to Sort:
  • Worst-case: can take a long time with $O(n^2)$
  • Average-case: also takes $O(n^2)$
  • Best-case: when already sorted, it takes $O(n)$
• Space Needed: It uses little extra space, $O(1)$.

How It Works:

1. Compare Two Items: Start at the front of the list and look at each pair of items side by side.
2. Swap If Needed: If the first item is bigger than the second, switch their places.
3. Keep Going: Do this for each pair in the list. By the time you finish one round, the largest item will have "bubbled" up to the end of the list.
4. Repeat: Do the same thing for the rest of the list, but skip the last sorted items.

Example:

Let’s look at a list: [5, 3, 8, 4, 2]

• First Pass: This changes it to [3, 5, 4, 2, 8]
• Second Pass: Now it looks like [3, 4, 2, 5, 8]
• Keep Going: Finally, it will be sorted like this: [2, 3, 4, 5, 8]

Bubble Sort is simple to understand, but it can be slow with a lot of items. That's why it's best for learning and for smaller lists.