Bubble Sort Time Complexity: Best, Average and Worst Case

from typing import List

def bubble_sort_naive(arr: List[int]) -> List[int]:
    """
    Naive bubble sort — always does n² comparisons.
    Time:  O(n²) all cases
    Space: O(1)
    """
    arr = arr.copy()
    n = len(arr)
    for i in range(n):
        for j in range(n - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr


def bubble_sort_optimised(arr: List[int]) -> List[int]:
    """
    Optimised bubble sort with two improvements:
    1. After pass i, the last i elements are in place — skip them.
    2. If no swap in a full pass, array is sorted — exit early.

    Time:  O(n) best case (already sorted)
           O(n²) average and worst case (random / reverse sorted)
    Space: O(1)
    """
    arr = arr.copy()
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):   # Each pass is shorter
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:   # No swaps → already sorted → done
            break
    return arr


# Already sorted — O(n): only 1 pass, exits immediately
print(bubble_sort_optimised([1, 2, 3, 4, 5]))
# [1, 2, 3, 4, 5]  — 1 pass

# Random — O(n²): multiple passes needed
print(bubble_sort_optimised([64, 34, 25, 12, 22, 11, 90]))
# [11, 12, 22, 25, 34, 64, 90]

# Reverse sorted — worst case O(n²): maximum swaps every pass
print(bubble_sort_optimised([5, 4, 3, 2, 1]))
# [1, 2, 3, 4, 5]  — all n passes required