# Bubble Sort

This blog covers:

* Introduction
    
* Step-by-step working of Bubble Sort
    
* Dry Run (Example)
    
* Code Implementation (in Python)
    
* Optimizations
    
* Merits
    
* Demerits
    

# 🔄 Bubble Sort – A Step-by-Step Guide for Beginners

Sorting is one of the most fundamental operations in computer science, and **Bubble Sort** is often the first algorithm introduced to beginners. While it's not the most efficient for large datasets, it's incredibly valuable for learning **how sorting algorithms work** under the hood.

In this blog, we’ll **break down Bubble Sort step-by-step** with examples, code, optimization tips, and its merits/demerits — all explained in simple language.

## 📘 What is Bubble Sort?

**Bubble Sort** is a simple comparison-based sorting algorithm. It repeatedly **swaps adjacent elements** if they are in the wrong order.

Imagine bubbling up the largest element to the top, just like bubbles rising to the surface of water — that's how the name "Bubble Sort" came into play.

## 🔍 Step-by-Step Working of Bubble Sort

Let’s sort an array in **ascending order** using Bubble Sort:

Example:  
`array = [5, 1, 4, 2, 8]`

### 🔄 Step 1: Outer Loop (Passes)

The algorithm goes through the array **N-1 times** (N = number of elements), where each pass places the next largest element in its correct position.

### 🔁 Step 2: Inner Loop (Comparisons)

In each pass, it compares adjacent pairs (`arr[j]` and `arr[j+1]`):

* If `array[j] > array[j+1]`, **swap them**
    
* Else, do nothing
    

### ✅ Step 3: Repeat Until Sorted

With each pass:

* The **largest unsorted element** moves to its correct position at the end
    
* Remaining unsorted elements are processed in the next pass
    

---

## 🧠 Dry Run (Example)

Let’s dry-run `array = [5, 1, 4, 2, 8]` step-by-step:

### 🔁 Pass 1:

* Compare 5 and 1 → Swap → `[1, 5, 4, 2, 8]`
    
* Compare 5 and 4 → Swap → `[1, 4, 5, 2, 8]`
    
* Compare 5 and 2 → Swap → `[1, 4, 2, 5, 8]`
    
* Compare 5 and 8 → No swap → `[1, 4, 2, 5, 8]`
    

✅ Largest element (8) is in the correct position

### 🔁 Pass 2:

* Compare 1 and 4 → No swap
    
* Compare 4 and 2 → Swap → `[1, 2, 4, 5, 8]`
    
* Compare 4 and 5 → No swap
    

✅ Second largest (5) is now in place

### 🔁 Pass 3:

* Compare 1 and 2 → No swap
    
* Compare 2 and 4 → No swap
    

✅ No swaps – array is now sorted!

---

## 💻 Python Code – Bubble Sort

```python
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):  # Outer loop
        for j in range(0, n - i - 1):  # Inner loop
            if arr[j] > arr[j + 1]:  # Compare and swap
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# Example usage
arr = [5, 1, 4, 2, 8]
sorted_arr = bubble_sort(arr)
print("Sorted array:", sorted_arr)
```

Output:

```plaintext
Sorted array: [1, 2, 4, 5, 8]
```

---

## ⚙️ Optimized Bubble Sort

The regular version does unnecessary passes **even if the array is already sorted**.

Let’s optimize it by adding a `swapped` flag. If no elements were swapped in a pass, we can **exit early**.

### ✅ Optimized Python Code:

```python
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 not swapped:  # No swap means array is sorted
            break
    return arr

# Example
arr = [1, 2, 3, 4, 5]
sorted_arr = optimized_bubble_sort(arr)
print("Sorted array:", sorted_arr)
```

✅ For already sorted or nearly sorted arrays, this is significantly faster.

---

## ✅ Merits of Bubble Sort

| Merit | Description |
| --- | --- |
| 🔹 Simple | Easy to understand and implement |
| 🔹 In-place | Doesn’t require extra memory |
| 🔹 Stable | Maintains the relative order of equal elements |
| 🔹 Educational | Great for teaching basic sorting logic |

---

## ❌ Demerits of Bubble Sort

| Demerit | Description |
| --- | --- |
| 🔸 Inefficient | Time complexity is **O(n²)** in worst and average case |
| 🔸 Slow for large data | Not suitable for real-time or large-scale sorting |
| 🔸 High number of swaps | More operations compared to efficient algorithms |

---

## 📊 Time and Space Complexity

| Case | Time Complexity |
| --- | --- |
| Best (sorted) | O(n) *(with optimization)* |
| Average | O(n²) |
| Worst | O(n²) |
| Space | O(1) *(no extra space needed)* |

---

## 🧾 Final Thoughts

Bubble Sort is **not used in production systems**, but it's still worth learning. It’s like **learning alphabets before writing sentences** — fundamental, simple, and educational.

Once you're comfortable with Bubble Sort, move on to faster algorithms like:

* **Selection Sort**
    
* **Insertion Sort**
    
* **Merge Sort**
    
* **Quick Sort**