Back to Arrays & Sorting

Bubble Sort

Bubble Sort is the simplest sorting algorithm. It works by repeatedly swapping adjacent elements if they are in the wrong order. Large values "bubble up" to the end of the array with each full pass.

         How it Works Step-by-Step:
        Start at index 0 and compare adjacent elements $A[j]$ and $A[j+1]$.
If $A[j] > A[j+1]$, swap them.
Move to the next pair and repeat until the end of the array.
After pass 1, the largest element is locked at the very last index.
Repeat for remaining unsorted elements until no swaps occur in a pass.

      

Python Implementation

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                # Swap elements
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        
        # Optimization: If no two elements were swapped in inner loop, array is sorted
        if not swapped:
            break
    return arr

Complexity Analysis

Best Case Time: $O(n)$ — Occurs when array is already sorted (with the swapped flag optimization).
Worst & Average Case Time: $O(n^2)$ — Occurs when the array is sorted in reverse order.
Space Complexity: $O(1)$ Auxiliary memory (In-place sort).
Stability: Stable (Equal values maintain their relative order).