Have you ever wondered how to sort a messy array of numbers in order? For example, turning [5, 3, 8, 4, 2] into [2, 3, 4, 5, 8]? Today, we’ll learn about Bubble Sort, one of the simplest sorting methods—you can master it in just 3 minutes!

What is Bubble Sort?¶

Imagine bubbles rising from the bottom of water to the surface. Bubble Sort gets its name from this “bubble rising” process: Every time we traverse the array, the largest element will “bubble up” to the end of the array, eventually completing the sorting.

For example, if we sort numbers from smallest to largest, Bubble Sort makes larger numbers “move backward” while smaller numbers “push forward,” just like bubbles rising in water.

Core Idea of Bubble Sort¶

1. Repeatedly compare adjacent elements: Start from the first element of the array, compare adjacent elements one by one. If the previous element is larger than the next, swap their positions.
2. “Bubbles” gradually rise: After each traversal, the largest element will “bubble up” to the last position of the array (its correct position). Thus, in the next traversal, we only need to compare up to the second-to-last element.
3. Early termination condition: If no swaps occur during a traversal, the array is already sorted, and we can terminate early.

Step-by-Step Example (Using [5, 3, 8, 4, 2])¶

Let’s use the array [5, 3, 8, 4, 2] to demonstrate the sorting process, with the goal of sorting it in ascending order.

Round 1: Let the largest number “bubble up” to the end¶

• Start comparing from the first element:
• Compare 5 and 3: 5 > 3, swap → [3, 5, 8, 4, 2]
• Compare 5 and 8: 5 < 8, no swap → no change
• Compare 8 and 4: 8 > 4, swap → [3, 5, 4, 8, 2]
• Compare 8 and 2: 8 > 2, swap → [3, 5, 4, 2, 8]
• Result: The largest number 8 has “bubbled up” to the end. The array becomes [3, 5, 4, 2, 8].

Round 2: Let the second-largest number “bubble up” to the second-to-last position¶

• Since 8 is already sorted, this round only needs to compare the first 4 elements:
• Compare 3 and 5: 3 < 5, no swap
• Compare 5 and 4: 5 > 4, swap → [3, 4, 5, 2, 8]
• Compare 5 and 2: 5 > 2, swap → [3, 4, 2, 5, 8]
• Result: The second-largest number 5 has “bubbled up” to the second-to-last position. The array becomes [3, 4, 2, 5, 8].

Round 3: Let the third-largest number “bubble up” to the third-to-last position¶

• Only compare the first 3 elements:
• Compare 3 and 4: 3 < 4, no swap
• Compare 4 and 2: 4 > 2, swap → [3, 2, 4, 5, 8]
• Result: The third-largest number 4 has “bubbled up” to the third-to-last position. The array becomes [3, 2, 4, 5, 8].

Round 4: Let the fourth-largest number “bubble up” to the fourth-to-last position¶

• Only compare the first 2 elements:
• Compare 3 and 2: 3 > 2, swap → [2, 3, 4, 5, 8]
• Result: The fourth-largest number 3 has “bubbled up” to the fourth-to-last position. The array becomes [2, 3, 4, 5, 8].

Round 5: Check if already sorted (early termination)¶

• The array [2, 3, 4, 5, 8] is now fully sorted. If we traverse again:
• Compare 2 and 3, 3 and 4, 4 and 5, 5 and 8—no swaps occur.
• Conclusion: Sorting is complete.

Key Optimization: Early Termination¶

If no swaps occur during a round, the array is already sorted, and we can stop early. For example, if the array is nearly sorted (e.g., [1, 3, 2, 4, 5]), Bubble Sort will terminate early in the second round, reducing unnecessary comparisons.

Time and Space Complexity¶

• Time Complexity: In the worst case (array is completely reversed), it requires n² comparisons and swaps. The average case is also O(n²) (where n is the array length).
• Space Complexity: Only constant extra space is needed (e.g., temporary variables for swaps), so it is O(1).

Summary¶

Bubble Sort’s essence is “comparing adjacent elements and swapping them,” gradually “bubbling up” larger elements to the end. It is simple to understand and implement, making it an excellent starting point to learn sorting algorithms. Although it is less efficient (suitable for small datasets), it helps you grasp the core logic of sorting, laying the foundation for more complex algorithms like Quick Sort or Merge Sort.

Try implementing Bubble Sort yourself with the array [6, 1, 7, 3, 2]—you’ll get the hang of it quickly!