Bubble Sort Algorithm
Bubble Sort repeatedly steps through an array, comparing adjacent elements and swapping them if they are in wrong order until the dataset is sorted.
Bubble Sort Worked Execution Trace
Pass 1 - First Compare & Swap (5, 1)
Compare adjacent elements 5 and 1. Since 5 > 1, swap them.
[5, 1, 4, 2, 8] -> 5 > 1 -> Swap -> [1, 5, 4, 2, 8]Pass 1 - Continuous Bubbling (5, 4 & 5, 2)
Compare (5, 4) -> Swap -> [1, 4, 5, 2, 8]. Compare (5, 2) -> Swap -> [1, 4, 2, 5, 8].
[1, 4, 2, 5, 8] -> Compare (5, 8) -> No swap needed.Pass 2 - Second Max Placement (4, 2)
Compare (1, 4) -> OK. Compare (4, 2) -> Swap -> [1, 2, 4, 5, 8].
Final Sorted Output: [1, 2, 4, 5, 8]Real-world analogy: Air Bubbles in Water
Larger air bubbles rise faster to the top of water. In bubble sort, the largest unsorted numbers bubble up to the right side with each pass.
- Adjacent Swap= If arr[j] > arr[j+1], swap them.
Complexity analysis
250,000 steps (Quadratic)
O(N²) Quadratic Time
O(1) In-Place Space
Memory growth rate as N expands.
Relative efficiency rating for large N.
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Best Case (Optimized) | O(N) | O(1) |
| Worst Case | O(N²) | O(1) |
Code implementations
function bubbleSort(arr) {
const n = arr.length;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}Real-world applications
Educational Tool
Teaches fundamental sorting and pointer concepts.
Nearly Sorted Arrays
Runs in O(N) when only 1 or 2 elements are misplaced.
Interview questions
Topic Knowledge Test & Assessment
Bubble Sort Algorithm Mastery Test
Evaluate your knowledge of adjacent comparison swaps, max element bubbling, and early exit optimizations.
Topic Metadata
Add an early exit `swapped` boolean check to stop the algorithm as soon as a full pass completes without any swaps!