📘 Bubble Sort (with Running Time Analysis)

1️⃣ Introduction

Bubble Sort is one of the simplest comparison-based sorting algorithms.

🔹 Idea

Repeatedly compare adjacent elements
Swap them if they are in the wrong order
Largest elements “bubble up” to the end

After each pass, the largest unsorted element is placed in its correct position.

2️⃣ Working Principle

🔹 Steps

Compare adjacent elements
Swap if left element > right element
Repeat for entire array
After each pass, ignore the last sorted element
Continue until array is sorted

3️⃣ Algorithm (Bubble Sort)

🔹 Pseudocode

BubbleSort(A, n):
   for i = 0 to n-2:
       for j = 0 to n-i-2:
           if A[j] > A[j+1]:
               swap A[j] and A[j+1]

🔹 Optimized Version (with flag)

BubbleSort(A, n):
   for i = 0 to n-2:
       swapped = false

       for j = 0 to n-i-2:
           if A[j] > A[j+1]:
               swap A[j], A[j+1]
               swapped = true

       if swapped == false:
           break

✔ Stops early if already sorted

4️⃣ Example (Step-by-Step)

🔹 Given Array:

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

🔹 Pass 1

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

🔹 Pass 2

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

🔹 Pass 3

[1, 2, 4, 5, 8]

✔ Sorted array

5️⃣ Running Time Analysis

🔹 Number of Comparisons

[
(n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2}
]

👉 Therefore:
[
T(n) = O(n^2)
]

6️⃣ Time Complexity

Case	Complexity
Best Case (Optimized)	O(n)
Average Case	O(n²)
Worst Case	O(n²)

7️⃣ Space Complexity

O(1) (in-place sorting)
No extra memory required

8️⃣ Characteristics of Bubble Sort

✔ Simple to understand
✔ Stable sorting algorithm
✔ In-place
✔ Adaptive (optimized version)

9️⃣ Advantages

Easy to implement
Useful for teaching
Works well for small datasets

🔟 Disadvantages

Very slow for large data
High number of comparisons
Not suitable for real-world applications

1️⃣1️⃣ Comparison with Other Sorting Algorithms

Algorithm	Time Complexity	Efficiency
Bubble Sort	O(n²)	Low
Insertion Sort	O(n²)	Moderate
Merge Sort	O(n log n)	High

🔚 Conclusion

Bubble Sort is a simple but inefficient sorting algorithm that repeatedly swaps adjacent elements until the array is sorted.

It is mainly used for educational purposes rather than real-world applications.

📌 Exam Tip

👉 Always include:

Adjacent comparison concept
Optimized version
Time complexity formula
Example

Bubble sort