Chapter 2: DSA Bubble Sort
DSA Bubble Sort – Let’s understand this sorting algorithm like your friend who is explaining it sitting next to you in the library — slowly, clearly, with real examples, step-by-step visuals, and honest comments about when you should actually use it.
What is Bubble Sort?
Bubble Sort is one of the simplest sorting algorithms to understand.
It works exactly like how many people sort playing cards in their hand:
- You look at two cards at a time
- If they are in the wrong order → you swap them
- You repeat this process many times until no more swaps are needed
In Bubble Sort, the name comes from the fact that with each full pass, the largest element slowly “bubbles up” to its correct position at the end (like bubbles rising in water).
How Bubble Sort Works – Step by Step
Imagine we have this array:
|
0 1 2 3 4 5 6 |
[5, 3, 8, 4, 2] |
Goal: Sort it in ascending order → [2, 3, 4, 5, 8]
Pass 1 (first complete round):
Compare adjacent elements and swap if left > right
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
5 3 8 4 2 ↑ 5 > 3 ? Yes → swap → 3 5 8 4 2 ↑ 5 < 8 ? No swap → 3 5 8 4 2 ↑ 8 > 4 ? Yes → swap → 3 5 4 8 2 ↑ 8 > 2 ? Yes → swap → 3 5 4 2 8 |
End of Pass 1: Largest number (8) is at the correct position (last position)
Now we know last position is sorted → we ignore it in next passes.
Pass 2:
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
3 5 4 2 | 8 (ignore 8) ↑ 3 < 5 ? No ↑ 5 > 4 ? Yes → swap → 3 4 5 2 | 8 ↑ 5 > 2 ? Yes → swap → 3 4 2 5 | 8 |
End of Pass 2: Second largest (5) is now in correct position
Pass 3:
|
0 1 2 3 4 5 6 7 8 9 10 11 12 |
3 4 2 | 5 8 ↑ 3 < 4 ? No ↑ 4 > 2 ? Yes → swap → 3 2 4 | 5 8 |
Pass 4:
|
0 1 2 3 4 5 6 7 8 9 |
3 2 | 4 5 8 ↑ 3 > 2 ? Yes → swap → 2 3 | 4 5 8 |
Now the array is sorted — no more swaps needed.
Bubble Sort – Visual Flow (very important to see the pattern)
Initial: 5 3 8 4 2
After pass 1: 3 5 4 2 8 ← largest bubbled to end
After pass 2: 3 4 2 5 8 ← second largest in place
After pass 3: 3 2 4 5 8
After pass 4: 2 3 4 5 8
Done!
Bubble Sort Code (Python – easiest version)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
def bubble_sort(arr): n = len(arr) # We do n-1 passes for i in range(n): # In each pass, we compare up to the unsorted part for j in range(0, n - i - 1): if arr[j] > arr[j + 1]: # Swap arr[j], arr[j + 1] = arr[j + 1], arr[j] return arr # Example numbers = [64, 34, 25, 12, 22, 11, 90] sorted_numbers = bubble_sort(numbers) print(sorted_numbers) # Output: [11, 12, 22, 25, 34, 64, 90] |
Important – Optimized Bubble Sort (very useful in interviews)
We can stop early if in any pass no swaps happened → that means array is already sorted!
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
def optimized_bubble_sort(arr): n = len(arr) for i in range(n): swapped = False for j in range(0, n - i - 1): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] swapped = True # If no swap happened in this pass → already sorted! if not swapped: break return arr |
This version is much faster on nearly sorted arrays.
Time & Space Complexity – Very Important for Interviews
| Case | Time Complexity | When does it happen? |
|---|---|---|
| Best Case | O(n) | Array is already sorted (with optimization) |
| Average Case | O(n²) | Random order |
| Worst Case | O(n²) | Reverse sorted array |
| Space Complexity | O(1) | Only uses constant extra space (in-place) |
When is Bubble Sort actually used in real life?
Almost never in serious programming.
But you should still learn it because:
- It is very easy to understand → helps build intuition for sorting
- Many interviewers ask to explain or write bubble sort in interviews (especially for freshers)
- It appears in many beginner coding sheets
- Helps you understand why we need better algorithms like Quick Sort, Merge Sort
Real sorting methods used in libraries:
- Python → Timsort (hybrid of merge + insertion)
- Java → Dual-Pivot Quick Sort / Timsort
- C++ → Introsort (hybrid)
Quick Comparison Table – Bubble Sort vs Others
| Algorithm | Best Time | Average Time | Worst Time | Stable? | In-place? |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | Yes | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | No | Yes |
| Insertion Sort | O(n) | O(n²) | O(n²) | Yes | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | Yes | No |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | No | Yes |
Summary – Bubble Sort in one sentence each
- Bubble Sort compares adjacent elements and swaps them if they are in wrong order
- In each pass, the largest remaining element bubbles to its correct position
- Very easy to understand and code
- Very slow — O(n²) in most cases
- Good only for learning and small arrays (n < 50–100)
- Almost never used in real projects
Do you want me to explain the next simple sorting algorithm in the same style? Options:
- Selection Sort (very similar but different logic)
- Insertion Sort (actually very useful in practice)
- How Bubble Sort compares to Insertion Sort with examples
- Common interview questions based on Bubble Sort logic
Just tell me which one you want next! 😊
