Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. Larger elements bubble up to their correct positions at the end of the list.

What is the time complexity of Bubble Sort?

Bubble Sort has O(n²) time complexity in the worst and average case. With early exit optimization, the best case is O(n) for already-sorted arrays. Space complexity is O(1).

Is Bubble Sort stable?

Yes, Bubble Sort is stable — equal elements maintain their relative order because swaps only occur when strictly greater, not when equal.

When should I use Bubble Sort?

Bubble Sort is best for educational purposes, very small datasets (n < 20), or nearly sorted arrays where early exit optimization makes it O(n). Avoid it for large datasets.

🫧 Bubble Sort Fundamentals

Q: What is Cocktail Shaker Sort?

Cocktail Shaker Sort (Bidirectional Bubble Sort) alternates between left-to-right and right-to-left passes, moving larger elements right and smaller elements left in each cycle.

🎯 What is Bubble Sort?

Bubble Sort is the simplest sorting algorithm that repeatedly steps through a list, compares adjacent elements, and swaps them if they're in the wrong order. The pass through the list is repeated until no swaps are needed. Larger elements "bubble up" to their correct position at the end of the list — hence the name.

Time Complexity: O(n²) | Space: O(1) | Stable: ✅ | In-Place: ✅

Deep Explanation

How it works: Each pass moves the largest unsorted element to its correct position at the end. After i passes, the last i elements are sorted. The algorithm gets its name because smaller elements "bubble" upward to the top, like air bubbles rising in water.

Why learn Bubble Sort? Despite its inefficiency for large datasets, Bubble Sort is excellent for teaching algorithm fundamentals: nested loops, swapping, early termination optimization, and stability concepts.

📌 Adjacent Comparison📌 In-Place Sorting📌 Stable Algorithm📌 Adaptive with Optimization

# Basic Bubble Sort Visualization
def bubble_sort_basic(arr):
    n = len(arr)
    for i in range(n):
        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

# Example
print(bubble_sort_basic([64, 34, 25, 12, 22, 11, 90]))
# Output: [11, 12, 22, 25, 34, 64, 90]

📐 Algorithm Walkthrough

🎯 Step-by-Step Process

For array [5, 1, 4, 2, 8]:

Pass 1: (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 at end
Pass 2: (1,4) no swap; (4,2)→swap→[1,2,4,5,8]; (4,5) no swap → 5 at correct position
Pass 3: (1,2) no swap; (2,4) no swap → array sorted

Visual Breakdown

After each complete pass, the largest unsorted element "bubbles up" to its final position. The algorithm performs n-1 passes in worst case, but optimizations can reduce this.

def bubble_sort_with_steps(arr):
    n = len(arr)
    for i in range(n):
        print(f"Pass {i+1}:")
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
            print(f"  {arr}")
    return arr

⏱️ Time & Space Complexity

🎯 Complexity Analysis

Worst-case (O(n²)): Reverse sorted array — maximum comparisons and swaps
Best-case (O(n)): Already sorted array — with optimization, only one pass
Average-case (O(n²)): Random order
Space Complexity: O(1) — only a constant amount of extra memory

Mathematical Derivation

Number of comparisons: (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n²). Number of swaps equals number of inversions (up to n(n-1)/2). Best-case with optimization: only n-1 comparisons.

⚡ Optimizations (Early Exit)

🎯 Flag-Based Optimization

If no swaps occur during a complete pass, the array is already sorted — we can terminate early.

Adaptive Bubble Sort

This optimization makes Bubble Sort adaptive — it runs in O(n) for nearly sorted arrays. This is the most practical version used in interviews.

def optimized_bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        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

🔄 Variants: Cocktail Shaker Sort

🎯 Bidirectional Bubble Sort

Cocktail Shaker Sort (Bidirectional Bubble Sort) alternates between left-to-right and right-to-left passes, moving larger elements right and smaller elements left in each cycle.

Performance Gains

This variant can reduce the number of passes by up to 50% for certain patterns, especially "turtles" (small elements at the end). Complexity remains O(n²) but constant factor improves.

def cocktail_shaker_sort(arr):
    n = len(arr)
    swapped = True
    start, end = 0, n - 1
    while swapped:
        swapped = False
        for i in range(start, end):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
        if not swapped: break
        swapped = False
        end -= 1
        for i in range(end - 1, start - 1, -1):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
        start += 1
    return arr

📊 Step-by-Step Visualization

🎯 Visual Example: [6, 3, 8, 2, 5]

Pass 1: [6,3]→swap [3,6,8,2,5]; [6,8] no swap; [8,2]→swap [3,6,2,8,5]; [8,5]→swap [3,6,2,5,8] ✓ 8 fixed
Pass 2: [3,6] no; [6,2]→swap [3,2,6,5,8]; [6,5]→swap [3,2,5,6,8] ✓ 6 fixed
Pass 3: [3,2]→swap [2,3,5,6,8]; [3,5] no → sorted!

💻 Multiple Implementations

# Using while loop
def bubble_sort_while(arr):
    n = len(arr)
    i = 0
    while i < n:
        j = 0
        while j < n - i - 1:
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
            j += 1
        i += 1
    return arr

# With early exit and reduced range
def bubble_sort_optimized_range(arr):
    n = len(arr)
    for i in range(n):
        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: return arr
    return arr

♻️ Recursive Bubble Sort

🎯 Recursive Implementation

Recursive approach: base case when n=1, otherwise perform one pass and recurse on n-1 elements.

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

🛡️ Stability & Adaptivity

🎯 Stable Sorting Property

Bubble Sort is stable — equal elements maintain their relative order. This is crucial when sorting by multiple keys (e.g., sort by name, then by age).

Why Stability Matters

When sorting objects with identical keys, stability ensures that the original order is preserved. Bubble Sort's adjacent swap only occurs when arr[j] > arr[j+1] (strictly greater), not when equal, preserving order of equal elements.

📈 Comparison with Other Sorts

vs Selection Sort: Both O(n²), but Bubble Sort is adaptive and stable
vs Insertion Sort: Insertion sort is generally faster and also adaptive
vs Quick/Merge Sort: O(n log n) dominates for large datasets
When to choose Bubble: Educational purposes, very small datasets (n<20), nearly sorted data with early exit

🎯 Use Cases & When to Use

✅ Teaching sorting fundamentals
✅ Nearly sorted arrays (adaptive optimization shines)
✅ Very small datasets (n < 20)
✅ When stable sorting is required and code simplicity matters
❌ Large datasets (use O(n log n) algorithms)
❌ Embedded systems with extreme memory constraints — but other O(n²) sorts like insertion sort are better

🔍 Loop Invariants Proof

🎯 Correctness Proof

Invariant: After i iterations of the outer loop, the last i elements are in their final sorted positions.

Initialization: i=0 → 0 elements sorted (trivially true).

Maintenance: Each inner pass moves the largest unsorted element to position n-i-1.

Termination: When i = n-1, all n elements are sorted.

🐍 Optimized Python Implementations

from typing import List, TypeVar
T = TypeVar('T')

def bubble_sort_with_sentinels(arr: List[T]) -> List[T]:
    n = len(arr)
    last_swap_index = n - 1
    while last_swap_index > 0:
        swapped = False
        new_last = 0
        for i in range(last_swap_index):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
                new_last = i
        if not swapped: break
        last_swap_index = new_last
    return arr

# Testing performance
import time
arr = list(range(1000, 0, -1))
start = time.time()
bubble_sort_with_sentinels(arr)
print(f"Sorted 1000 elements in {time.time()-start:.4f}s")

💪 Practice & Problem Patterns

🎯 Common Variations

Odd-Even Sort: Parallel version of bubble sort
Comb Sort: Bubble sort with gap (improved performance)
Sorting Linked Lists: Bubble sort works naturally on linked lists
LeetCode Problems: 75. Sort Colors (Dutch National Flag) — variant of bubble logic

Interview Challenge: Detect Already Sorted

Write a function that returns True if the array can be sorted with at most one swap (using bubble sort logic to detect inversions).