BUBBLE SORT CONCEPT AND ALGORITHM

BUBBLE SORT CONCEPT AND ALGORITHM

🎯 What is Bubble Sort?

Bubble Sort is a simple sorting algorithm that repeatedly compares adjacent elements and swaps them if they are in the wrong order.

Large elements “bubble up” to the end of the list, like bubbles in water — hence the name.

---

📌 Definition

Bubble Sort is a comparison-based sorting algorithm in which adjacent elements are repeatedly swapped if they are in the wrong order until the array becomes sorted.

---

🧠 How Bubble Sort Works

Steps:

1. Compare first two elements
2. Swap if left > right
3. Move one position ahead
4. Repeat for entire array
5. After each pass, largest element moves to the end
6. Repeat until sorted

---

📊 Example

Unsorted Array:

A = [5, 1, 4, 2, 8]

---

🔁 Pass 1

Comparison	Action
5 > 1	Swap → [1, 5, 4, 2, 8]
5 > 4	Swap → [1, 4, 5, 2, 8]
5 > 2	Swap → [1, 4, 2, 5, 8]
5 < 8	No swap

👉 Largest (8) is in correct position

---

🔁 Pass 2

Comparison	Action
1 < 4	No swap
4 > 2	Swap → [1, 2, 4, 5, 8]
4 < 5	No swap

---

🔁 Pass 3

No swaps needed → array already sorted

---

📌 Final Sorted Array

[1, 2, 4, 5, 8]

---

💻 Algorithm (Pseudocode)

BubbleSort(A, n)

1. for i = 0 to n-1
2.     for j = 0 to n-i-2
3.         if A[j] > A[j+1]
4.             swap(A[j], A[j+1])

---

🐍 Python Program for Bubble Sort

def bubble_sort(arr):
    n = len(arr)

    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

    return arr

# Example
arr = [5, 1, 4, 2, 8]

result = bubble_sort(arr)

print("Sorted Array:", result)

---

Output:

Sorted Array: [1, 2, 4, 5, 8]

---

⚡ Time Complexity

Case	Complexity
Best Case	O(n) (already sorted)
Worst Case	O(n²)
Average Case	O(n²)

---

📊 Space Complexity

• O(1) (no extra memory used)

---

🆚 Bubble Sort vs Other Sorting

Feature	Bubble Sort	Selection Sort	Insertion Sort
Speed	Slow	Slow	Medium
Complexity	O(n²)	O(n²)	O(n²)
Stability	Yes	No	Yes
Best Use	Small data	Small data	Nearly sorted data

---

📌 Advantages

• Very simple to understand
• Easy to implement
• No extra memory required
• Stable sorting algorithm

---

❌ Disadvantages

• Very slow for large datasets
• Many unnecessary comparisons
• Not efficient for real applications

---

🧠 Real Life Example

• Sorting playing cards in hand 🃏
• Arranging books by height 📚

---

📌 Summary

• Bubble Sort compares adjacent elements
• Largest elements move to the end after each pass
• Time complexity is O(n²)
• Simple but inefficient for large datasets

---

❓ Important Questions

Short Questions

1. What is bubble sort?
2. Why is it called bubble sort?
3. What is time complexity of bubble sort?
4. Is bubble sort stable?
5. Give one example.

---

Long Questions

1. Explain bubble sort with example.
2. Write algorithm of bubble sort.
3. Write Python program for bubble sort.
4. Compare bubble sort with selection sort.
5. Explain best and worst case of bubble sort.