Bubble Sort
A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.
Ready to sort
Intuition
Imagine air bubbles rising to the surface of water. The larger bubbles rise faster. Similarly, in Bubble Sort, the largest elements "bubble" to the top (end of the array) by repeatedly swapping with their neighbors.
Concept
Bubble Sort is a simple comparison-based algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.
How it Works
- Start at the beginning of the array.
- Compare the first two elements. If the first is greater than the second, swap them.
- Move to the next pair and repeat.
- After one full pass, the largest element is guaranteed to be at the end.
- Repeat the process for the remaining unsorted elements.
Step-by-Step Breakdown
- Compare: Look at two neighbors.
- Swap?: If Left > Right, switch places.
- Move: Shift one step to the right.
- Repeat: Keep doing this until the biggest number reaches the end.
Trace: [5, 3, 8, 4, 2]
Compare 5 > 3? YES
[3, 5, 8, 4, 2]
Compare 5 > 8? success
[3, 5, 8, 4, 2]
Compare 8 > 4? YES
[3, 5, 4, 8, 2]
Compare 8 > 2? YES
[3, 5, 4, 2, 8]
Pass 1 Complete: Largest element (8) is now sorted!
When to Use
- Educational Purposes: It's the simplest algorithm to implement and understand concepts like swapping.
- Small Datasets: When N is very small (e.g., < 20), the O(n²) penalty is negligible.
- Nearly Sorted Data: With the "swapped" flag optimization, it runs in O(n) for already sorted arrays.
When NOT to Use
- Large Datasets: O(n²) complexity makes it impractical for N > 10,000.
- Performance Critical Systems: Merge Sort or Quick Sort are significantly faster (O(n log n)).
How to Identify
You likely won't use Bubble Sort directly in an interview unless asked, but you might need the "adjacent swap" concept. If a problem asks for the "minimum number of adjacent swaps to sort an array", it is directly related to the number of inversions.
Frequently Asked Questions
Why is it called "Bubble Sort"?
The algorithm gets its name because smaller elements "bubble" to the top while larger elements sink to the bottom, much like bubbles in water.
Is Bubble Sort stable?
Yes, Bubble Sort is a stable sorting algorithm. It maintains the relative order of equal elements.
What is the time complexity of Bubble Sort?
The average and worst-case time complexity is O(n²). However, with a "swapped" flag optimization, the best-case complexity for a sorted array is O(n).