Bubble Sort: Foundations & Optimization

# Bubble Sort: Complete Implementation & Analysis
# Author: ZeyLearn
# Topic: Sorting Algorithms - Bubble Sort with Optimizations
import time
import random
from typing import List, Tuple
print("=" * 80)
print("BUBBLE SORT: COMPREHENSIVE IMPLEMENTATION")
print("=" * 80)
print()
# ==============================================================================
# 1. BASIC BUBBLE SORT (Unoptimized)
# ==============================================================================
def bubble_sort_basic(arr: List[int]) -> List[int]:
    """
    Basic Bubble Sort implementation without optimizations.
    
    Time Complexity: O(n²) for all cases
    Space Complexity: O(1)
    Stable: Yes
    
    Args:
        arr: List of integers to sort
    
    Returns:
        Sorted list (in-place modification)
    """
    n = len(arr)
    
    # Outer loop: n passes through the array
    for i in range(n):
        # Inner loop: compare adjacent elements
        # Each pass reduces range by 1 (last i elements already sorted)
        for j in range(n - i - 1):
            # Compare adjacent elements
            if arr[j] > arr[j + 1]:
                # Swap if out of order
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    
    return arr
print("1. BASIC BUBBLE SORT (Unoptimized)")
print("-" * 80)
test_array = [64, 34, 25, 12, 22, 11, 90]
print(f"Original array: {test_array}")
result = bubble_sort_basic(test_array.copy())
print(f"Sorted array:   {result}")
print()
# ==============================================================================
# 2. OPTIMIZED BUBBLE SORT (Early Termination)
# ==============================================================================
def bubble_sort_optimized(arr: List[int]) -> Tuple[List[int], int]:
    """
    Optimized Bubble Sort with early termination.
    
    Optimization: Stops if no swaps occur (array is sorted).
    
    Time Complexity: 
        - Best: O(n) - already sorted
        - Average: O(n²)
        - Worst: O(n²) - reverse sorted
    
    Space Complexity: O(1)
    
    Args:
        arr: List of integers to sort
    
    Returns:
        Tuple of (sorted list, number of passes performed)
    """
    n = len(arr)
    passes = 0
    
    for i in range(n):
        swapped = False  # Flag to track if any swap occurred
        passes += 1
        
        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
        
        # Early termination: if no swaps, array is sorted
        if not swapped:
            print(f"  ✓ Array sorted after {passes} pass(es) (early termination)")
            break
    
    return arr, passes
print("2. OPTIMIZED BUBBLE SORT (Early Termination)")
print("-" * 80)
# Test with nearly-sorted array
nearly_sorted = [1, 2, 4, 3, 5, 6, 7]
print(f"Nearly-sorted array: {nearly_sorted}")
result, passes = bubble_sort_optimized(nearly_sorted.copy())
print(f"Sorted array:        {result}")
print(f"Total passes: {passes}/{len(nearly_sorted)} (saved {len(nearly_sorted) - passes} passes!)")
print()
# ==============================================================================
# 3. BUBBLE SORT WITH DETAILED STEP TRACKING
# ==============================================================================
def bubble_sort_verbose(arr: List[int], show_steps: bool = True) -> List[int]:
    """
    Bubble Sort with detailed step-by-step output.
    Perfect for learning and visualization.
    
    Args:
        arr: List to sort
        show_steps: Whether to print each step
    
    Returns:
        Sorted list
    """
    n = len(arr)
    
    if show_steps:
        print(f"Initial array: {arr}")
        print()
    
    for i in range(n):
        swapped = False
        swap_count = 0
        
        if show_steps:
            print(f"Pass {i + 1}:")
        
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                # Show comparison and swap
                if show_steps:
                    print(f"  Compare arr[{j}]={arr[j]} and arr[{j+1}]={arr[j+1]} → SWAP")
                
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
                swap_count += 1
            elif show_steps:
                print(f"  Compare arr[{j}]={arr[j]} and arr[{j+1}]={arr[j+1]} → No swap")
        
        if show_steps:
            print(f"  After pass {i + 1}: {arr} ({swap_count} swaps)")
            print()
        
        if not swapped:
            if show_steps:
                print(f"✓ No swaps in pass {i + 1} - Array is sorted!")
            break
    
    return arr
print("3. BUBBLE SORT WITH STEP TRACKING")
print("-" * 80)
small_array = [5, 2, 8, 1, 9]
print(f"Demonstrating step-by-step sorting:
")
bubble_sort_verbose(small_array.copy(), show_steps=True)
print()
# ==============================================================================
# 4. BUBBLE SORT WITH SWAP COUNTER
# ==============================================================================
def bubble_sort_count_swaps(arr: List[int]) -> Tuple[List[int], int]:
    """
    Bubble Sort that counts total number of swaps.
    Useful for analyzing worst-case behavior.
    
    Returns:
        Tuple of (sorted array, total swap count)
    """
    n = len(arr)
    total_swaps = 0
    
    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]
                total_swaps += 1
                swapped = True
        
        if not swapped:
            break
    
    return arr, total_swaps
print("4. SWAP COUNT ANALYSIS")
print("-" * 80)
test_cases = [
    ([1, 2, 3, 4, 5], "Already sorted (Best case)"),
    ([3, 1, 4, 2, 5], "Random order (Average case)"),
    ([5, 4, 3, 2, 1], "Reverse sorted (Worst case)")
]
for arr, description in test_cases:
    sorted_arr, swaps = bubble_sort_count_swaps(arr.copy())
    print(f"{description}:")
    print(f"  Input:  {arr}")
    print(f"  Output: {sorted_arr}")
    print(f"  Swaps:  {swaps}")
    print()
# ==============================================================================
# 5. DESCENDING ORDER BUBBLE SORT
# ==============================================================================
def bubble_sort_descending(arr: List[int]) -> List[int]:
    """
    Bubble Sort in descending order (largest to smallest).
    
    Simply reverse the comparison operator!
    """
    n = len(arr)
    
    for i in range(n):
        swapped = False
        
        for j in range(n - i - 1):
            # Changed > to < for descending order
            if arr[j] < arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        
        if not swapped:
            break
    
    return arr
print("5. DESCENDING ORDER BUBBLE SORT")
print("-" * 80)
desc_array = [5, 2, 8, 1, 9, 3]
print(f"Original: {desc_array}")
print(f"Descending: {bubble_sort_descending(desc_array.copy())}")
print()
# ==============================================================================
# 6. CUSTOM COMPARATOR BUBBLE SORT
# ==============================================================================
def bubble_sort_custom(arr: List, key=None) -> List:
    """
    Bubble Sort with custom comparison key.
    
    Args:
        arr: List to sort
        key: Function to extract comparison key (like Python's sorted())
    
    Example:
        bubble_sort_custom([(1, 'b'), (2, 'a')], key=lambda x: x[1])
    """
    n = len(arr)
    
    # Default key is identity function
    if key is None:
        key = lambda x: x
    
    for i in range(n):
        swapped = False
        
        for j in range(n - i - 1):
            # Use key function for comparison
            if key(arr[j]) > key(arr[j + 1]):
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        
        if not swapped:
            break
    
    return arr
print("6. CUSTOM COMPARATOR (Sort by Second Element)")
print("-" * 80)
tuples = [("Alice", 30), ("Bob", 25), ("Charlie", 35), ("Diana", 28)]
print(f"Original: {tuples}")
sorted_by_age = bubble_sort_custom(tuples.copy(), key=lambda x: x[1])
print(f"Sorted by age: {sorted_by_age}")
print()
# ==============================================================================
# 7. PERFORMANCE COMPARISON
# ==============================================================================
def measure_performance(sort_func, arr: List[int]) -> float:
    """Measure execution time of sorting function."""
    arr_copy = arr.copy()
    start_time = time.perf_counter()
    sort_func(arr_copy)
    end_time = time.perf_counter()
    return (end_time - start_time) * 1000  # Convert to milliseconds
print("7. PERFORMANCE ANALYSIS")
print("-" * 80)
# Generate test arrays of different sizes
sizes = [10, 50, 100, 500]
print("Comparing Basic vs Optimized Bubble Sort:
")
print(f"{'Size':<10} {'Basic (ms)':<15} {'Optimized (ms)':<15} {'Improvement':<15}")
print("-" * 60)
for size in sizes:
    # Random array for fair comparison
    test_arr = [random.randint(1, 1000) for _ in range(size)]
    
    basic_time = measure_performance(bubble_sort_basic, test_arr)
    optimized_time = measure_performance(
        lambda arr: bubble_sort_optimized(arr)[0], 
        test_arr
    )
    
    improvement = ((basic_time - optimized_time) / basic_time) * 100
    
    print(f"{size:<10} {basic_time:<15.4f} {optimized_time:<15.4f} {improvement:>6.2f}%")
print()
# ==============================================================================
# 8. EDGE CASES & ROBUSTNESS
# ==============================================================================
print("8. EDGE CASES & ROBUSTNESS TESTING")
print("-" * 80)
edge_cases = [
    ([], "Empty array"),
    ([42], "Single element"),
    ([1, 1, 1, 1], "All duplicates"),
    ([1, 2, 2, 3, 3, 3], "Some duplicates"),
    ([-5, -1, -10, 0, 3], "Negative numbers"),
    ([1000000, 1, 500000], "Large numbers")
]
for arr, description in edge_cases:
    original = arr.copy()
    sorted_arr = bubble_sort_optimized(arr.copy())[0]
    print(f"{description}:")
    print(f"  Input:  {original}")
    print(f"  Output: {sorted_arr}")
    print()
# ==============================================================================
# 9. TIME COMPLEXITY DEMONSTRATION
# ==============================================================================
print("9. TIME COMPLEXITY PROOF (Empirical)")
print("-" * 80)
print("Measuring growth rate as array size doubles:
")
print(f"{'Size (n)':<10} {'Time (ms)':<15} {'Ratio (T₂/T₁)':<15}")
print("-" * 45)
prev_time = None
prev_size = None
for n in [100, 200, 400, 800]:
    arr = [random.randint(1, 1000) for _ in range(n)]
    exec_time = measure_performance(bubble_sort_basic, arr)
    
    if prev_time is not None:
        ratio = exec_time / prev_time
        expected_ratio = (n / prev_size) ** 2  # O(n²) prediction
        print(f"{n:<10} {exec_time:<15.4f} {ratio:>6.2f}x (expected ~{expected_ratio:.1f}x)")
    else:
        print(f"{n:<10} {exec_time:<15.4f} {'-':<15}")
    
    prev_time = exec_time
    prev_size = n
print()
print("✓ Notice: When n doubles, time roughly quadruples → confirms O(n²)")
print()
# ==============================================================================
# FINAL SUMMARY
# ==============================================================================
print("=" * 80)
print("BUBBLE SORT SUMMARY")
print("=" * 80)
print("""
✅ Key Concepts Demonstrated:
   1. Basic iterative swapping algorithm
   2. Optimization with early termination flag
   3. Step-by-step execution tracking
   4. Swap counting and analysis
   5. Custom comparators (key functions)
   6. Edge case handling
   7. Empirical time complexity verification
📊 Complexity Analysis:
   • Best Case:    O(n)   - with optimization, sorted input
   • Average Case: O(n²)  - random input
   • Worst Case:   O(n²)  - reverse sorted input
   • Space:        O(1)   - in-place sorting
   • Stable:       Yes ✅ - maintains relative order
🎯 When to Use:
   • Educational purposes (learning sorting algorithms)
   • Small datasets (n < 50)
   • Nearly-sorted data (takes advantage of O(n) best case)
   
⚠️  When NOT to Use:
   • Large datasets (use Quick Sort, Merge Sort, or Tim Sort)
   • Production systems (use built-in sort functions)
   • Performance-critical applications
💡 Pro Tips:
   1. Always use the optimized version with early termination
   2. Remember loop bounds: range(n - i - 1)
   3. Test edge cases: empty, single element, duplicates
   4. Understand WHY it's O(n²) - applies to algorithm analysis!
🚀 Next Steps:
   → Selection Sort (fewer swaps)
   → Insertion Sort (better for small/nearly-sorted data)
   → Merge Sort (O(n log n) guaranteed)
   → Quick Sort (fastest average case)
""")
print("=" * 80)
print("End of Bubble Sort Implementation")
print("=" * 80)