Bubble Sort — Data Structures -

💧 What Is Bubble Sort?

Bubble Sort is a sorting algorithm that arranges elements (numbers, names, etc.) in ascending or descending order.

It works just like bubbles rising in water — bigger bubbles slowly move up to the top while smaller ones sink below.
In the same way, Bubble Sort compares and swaps nearby elements so that, step by step, the largest (or smallest) value “bubbles up” to its correct position.

Basic Idea in Simple Words

Here’s the logic:

Look at two neighboring elements.
If they’re in the wrong order, swap them.
Move to the next pair and repeat.
After one complete pass, the largest element will be at the end (if sorting in ascending order).
Then, repeat the process for the remaining elements until the whole list is sorted.

Each round of comparisons is called a pass, and with every pass, the next largest element settles at the end — just like bubbles rising one by one.

🌸 Step-by-Step Example

Let’s say we have this list of numbers:

[5, 3, 8, 4, 2]

We want to sort it in ascending order (small to big).

🔹 Pass 1:

Compare each pair and swap if needed.

Comparison	Action	Result
5 & 3	5 > 3 → swap	[3, 5, 8, 4, 2]
5 & 8	5 < 8 → no swap	[3, 5, 8, 4, 2]
8 & 4	8 > 4 → swap	[3, 5, 4, 8, 2]
8 & 2	8 > 2 → swap	[3, 5, 4, 2, 8]

👉 After Pass 1: the largest element (8) moves to the last position.

🔹 Pass 2:

Now, we ignore the last element (since 8 is already sorted).

Comparison	Action	Result
3 & 5	3 < 5 → no swap	[3, 5, 4, 2, 8]
5 & 4	5 > 4 → swap	[3, 4, 5, 2, 8]
5 & 2	5 > 2 → swap	[3, 4, 2, 5, 8]

👉 After Pass 2: 5 is now in its correct position.

🔹 Pass 3:

Compare first three pairs only.

Comparison	Action	Result
3 & 4	3 < 4 → no swap	[3, 4, 2, 5, 8]
4 & 2	4 > 2 → swap	[3, 2, 4, 5, 8]

👉 After Pass 3: 4 is now correctly placed.

🔹 Pass 4:

Last few checks.

Comparison	Action	Result
3 & 2	3 > 2 → swap	[2, 3, 4, 5, 8]

✨ Done! The list is fully sorted.

🪄 Visual Diagram of Bubble Sort

Initial:      [5, 3, 8, 4, 2]
After Pass 1: [3, 5, 4, 2, 8]
After Pass 2: [3, 4, 2, 5, 8]
After Pass 3: [3, 2, 4, 5, 8]
After Pass 4: [2, 3, 4, 5, 8]

You can imagine each number as a soap bubble in water — with every round, the biggest one pops up to the surface. 🌊

⚙️ Algorithm (in simple pseudocode)

for i from 0 to n-1:
    for j from 0 to n-i-2:
        if arr[j] > arr[j+1]:
            swap(arr[j], arr[j+1])

Meaning:

Outer loop = number of passes.
Inner loop = compares neighboring pairs.
Swap = when the left one is bigger than the right one.

💡 Time Complexity

Case	Time Complexity	Explanation
Best Case	O(n)	When array is already sorted.
Average Case	O(n²)	Normal case with some disorder.
Worst Case	O(n²)	When array is completely reversed.

Space Complexity:

O(1) → Only a few temporary variables are used for swapping.

🌼 Advantages and Disadvantages

Advantages	Disadvantages
Simple and easy to understand.	Very slow for large lists.
Requires very little memory.	Performs many unnecessary swaps.
Good for learning basic sorting logic.	Not efficient compared to modern algorithms like Quick Sort or Merge Sort.

🎯 When to Use Bubble Sort

When your dataset is small or almost sorted.
When you want to teach or learn how sorting logic works.
When code simplicity is more important than speed.

🌟 Real-Life Analogy

Imagine arranging books by height on a shelf.
You look at two books at a time — if the left one is taller than the right one, you swap them.
By the time you reach the end of the shelf, the tallest book ends up at the end.
Then, you start again, ignoring the last book since it’s already in place.
Keep doing this until everything is in perfect order. 📚