A simple sorting algorithm that repeatedly walks through the list, compares each pair of adjacent elements, and swaps them if they are in the wrong order. Bubble sort is easy to understand and implement, making it an excellent teaching example for understanding how sorting works.
Definition
A simple sorting algorithm that repeatedly walks through the list, compares each pair of adjacent elements, and swaps them if they are in the wrong order. This process repeats until no more swaps are needed, meaning the list is fully sorted.
💡 Intuition
Heavier bubbles sink and lighter bubbles rise — larger values slowly move to the end of the list.
🎯 Core Idea
Each pass moves the largest unsorted element to its correct position at the end.
Example
Formula
🌟 Why It Matters
Bubble sort is easy to understand and implement, making it an excellent teaching example for understanding how sorting works. However, its O(n^2) performance makes it impractical for large datasets, which is why more efficient algorithms like merge sort are used in practice.
💭 Hint When Stuck
To trace bubble sort, make repeated passes through the list. On each pass, compare every pair of adjacent elements and swap if the left is greater. After each pass, the largest unsorted value is in its final position. Stop when a full pass makes no swaps.
Formal View
Related Concepts
🚧 Common Stuck Point
Bubble sort is O(n²) — avoid it for large data; use merge sort or quick sort instead.
⚠️ Common Mistakes
- Not optimizing with an early exit—if a pass makes no swaps, the list is already sorted and you can stop
- Comparing elements beyond the sorted portion at the end of the array, wasting comparisons
- Using bubble sort for large datasets when O(n \log n) algorithms are available and dramatically faster
Frequently Asked Questions
What is Bubble Sort in CS Thinking?
A simple sorting algorithm that repeatedly walks through the list, compares each pair of adjacent elements, and swaps them if they are in the wrong order. This process repeats until no more swaps are needed, meaning the list is fully sorted.
What is the Bubble Sort formula?
When do you use Bubble Sort?
To trace bubble sort, make repeated passes through the list. On each pass, compare every pair of adjacent elements and swap if the left is greater. After each pass, the largest unsorted value is in its final position. Stop when a full pass makes no swaps.
Prerequisites
Next Steps
How Bubble Sort Connects to Other Ideas
To understand bubble sort, you should first be comfortable with sorting, iteration and efficiency. Once you have a solid grasp of bubble sort, you can move on to merge sort.