Bubble sort is a simple and straightforward sorting algorithm that compares two adjacent elements in the list and swaps them if they are in the wrong order. This process is repeated until the entire list is sorted.

Interactive Bubble Sort Visualizer

Try the interactive visualizer below to see how bubble sort works step by step!

Interactive Bubble Sort Visualizer

Speed: 1000ms

64

34

25

12

22

11

90

Normal

Comparing

Swapping

Sorted

How to use:

• Click Play to watch the bubble sort algorithm in action
• Adjust the speed slider to control animation speed
• Click Reset to return to the original array
• Colors indicate: Normal (blue), Comparing (yellow), Swapping (red), Sorted (green)

Time Complexity Analysis

Best Case: O(n)

Already sorted array

Average Case: O(n²)

Random order

Worst Case: O(n²)

Reverse sorted

n=10

n=20

n=50

n=100

n=200

n=500

Best O(n)

Average O(n²)

Worst O(n²)

Python Implementation Examples

📝 Basic Implementation

def bubble_sort_basic(arr):
    """Basic bubble sort - O(n²) for all cases"""
    n = len(arr)
    
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    
    return arr

# Example usage
numbers = [64, 34, 25, 12, 22, 11, 90]
result = bubble_sort_basic(numbers.copy())
print(result)  # [11, 12, 22, 25, 34, 64, 90]

⚡ Optimized with Early Termination

def bubble_sort_optimized(arr):
    """Optimized bubble sort with early termination"""
    n = len(arr)
    
    for i in range(n):
        swapped = False
        
        for j in range(0, 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 occurred
        if not swapped:
            break
    
    return arr

🔍 Explanation

The bubble_sort_basic function implements the basic bubble sort algorithm with a time complexity of O(n²) for all cases. The bubble_sort_optimized function adds an early termination condition to improve performance, especially for nearly sorted arrays.

Both functions take an array as input and return the sorted array. The optimized version checks if any swaps were made in each pass; if no swaps occur, it terminates early, indicating that the array is already sorted.

How Bubble Sort Works

Bubble sort works by repeatedly stepping through the list, comparing adjacent elements and swapping them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

Algorithm Steps:

1. Compare adjacent elements
2. Swap them if they are in wrong order
3. Repeat for all elements
4. Continue until no swaps are needed

Time Complexity:

• Best Case: O(n) - when array is already sorted
• Average Case: O(n²) - random order
• Worst Case: O(n²) - reverse sorted array

Space Complexity: O(1) - only uses constant extra space