Bubble Sort in DSA: A Beginner-Friendly Guide

Sorting is one of the most fundamental problems in computer science, and Bubble Sort is often the very first algorithm students encounter. While it’s not the fastest, it’s a great way to understand how sorting works step by step.

---

🔹 What is Bubble Sort?

Bubble Sort is a simple comparison-based algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

The name comes from the way larger elements “bubble up” to the end of the list with each pass, just like bubbles rising to the surface of water.

---

🔹 How Bubble Sort Works (Step by Step)

1. Start at the beginning of the array.
2. Compare the current element with the next one.
3. If the current element is greater, swap them.
4. Move to the next pair and repeat until the end of the array.
5. After the first pass, the largest element is at the end.
6. Repeat the process for the remaining unsorted part of the array.

👉 After n-1 passes, the array is fully sorted.

---

🔹 Example Walkthrough

Let’s sort this array:

[7, 12, 9, 11, 3]

• Compare 7 and 12 → no swap
• Compare 12 and 9 → swap → [7, 9, 12, 11, 3]
• Compare 12 and 11 → swap → [7, 9, 11, 12, 3]
• Compare 12 and 3 → swap → [7, 9, 11, 3, 12]

At the end of the first pass, 12 has bubbled to the end. The process repeats until the array is sorted.

---

🔹 Bubble Sort Implementation (Python Example)

def bubble_sort(arr):
    n = len(arr)
    for i in range(n-1):
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

print(bubble_sort([64, 34, 25, 12, 22, 11, 90, 5]))

✅ Output: [5, 11, 12, 22, 25, 34, 64, 90]

---

🔹 Optimized Bubble Sort

If no swaps happen in a pass, the array is already sorted. We can stop early:

def optimized_bubble_sort(arr):
    n = len(arr)
    for i in range(n-1):
        swapped = False
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

This small tweak saves time when the array is nearly sorted.

---

🔹 Time Complexity of Bubble Sort

Case	Comparisons	Time Complexity
Best Case	n-1	O(n) (when already sorted)
Average Case	~n²/2	O(n²)
Worst Case	n²	O(n²)

• Space Complexity: O(1) (in-place sorting)
• Stability: Yes (doesn’t change the order of equal elements)

---

🔹 When to Use Bubble Sort?

• ✅ Teaching and learning sorting basics
• ✅ Small datasets where simplicity matters more than speed
• ❌ Not suitable for large datasets (use QuickSort, MergeSort, or HeapSort instead)

---

🌟 Key Takeaways

• Bubble Sort is simple but inefficient for large inputs.
• It’s a great introductory algorithm to understand sorting logic.
• Optimized Bubble Sort can stop early if the array is already sorted.

---