Understanding Bubble Sort

Back to: Python Data Structure and Algorithims

Understanding Bubble Sort

Bubble Sort is one of the simplest sorting algorithms, perfect for learning the basic concepts of sorting.
In this algorithm, we repeatedly compare adjacent items and swap them if they are in the wrong order. This way, the largest items “bubble up” to the end of the list in each pass.

---

Step 1: Example List

Let’s start with an example list:

We want to sort this in ascending order.

---

Step 2: Compare and Swap

1. First Pass: Compare adjacent items from the start.

   • Compare 6 and 3 → swap → [3, 6, 5, 2, 4, 1]

   • Compare 6 and 5 → swap → [3, 5, 6, 2, 4, 1]

   • Compare 6 and 2 → swap → [3, 5, 2, 6, 4, 1]

   • Compare 6 and 4 → swap → [3, 5, 2, 4, 6, 1]

   • Compare 6 and 1 → swap → [3, 5, 2, 4, 1, 6]

Observation: The largest element, 6, has now “bubbled up” to the last position.

---

2. Second Pass: Repeat for remaining items (excluding last sorted item).

   • Compare 3 and 5 → no swap → [3, 5, 2, 4, 1, 6]

   • Compare 5 and 2 → swap → [3, 2, 5, 4, 1, 6]

   • Compare 5 and 4 → swap → [3, 2, 4, 5, 1, 6]

   • Compare 5 and 1 → swap → [3, 2, 4, 1, 5, 6]

Observation: The second largest element, 5, is now in the correct position.

---

3. Third Pass: Continue bubbling up.

   • Compare 3 and 2 → swap → [2, 3, 4, 1, 5, 6]

   • Compare 3 and 4 → no swap → [2, 3, 4, 1, 5, 6]

   • Compare 4 and 1 → swap → [2, 3, 1, 4, 5, 6]

---

4. Fourth Pass:

   • Compare 2 and 3 → no swap → [2, 3, 1, 4, 5, 6]

   • Compare 3 and 1 → swap → [2, 1, 3, 4, 5, 6]

---

5. Fifth Pass:

   • Compare 2 and 1 → swap → [1, 2, 3, 4, 5, 6]

Now the list is fully sorted.

---

Step 3: Key Points

• How it works: Each pass bubbles the largest unsorted element to its correct position.

• Number of comparisons:

  • 1st pass: n-1 comparisons

  • 2nd pass: n-2 comparisons

  • And so on…

• Time Complexity:

  • Worst-case: O(n²)

  • Best-case (already sorted): O(n)

• Space Complexity: O(1) (in-place sorting)

---

Step 4: Visualization Summary

---

Bubble Sort is simple, but inefficient for large lists, which is why algorithms like Merge Sort and Quicksort are preferred in practice.