Bubble Sort Algorithm Tutorial

Bubble Sort

Bubble Sort is a simple comparison-based sorting algorithm that repeatedly swaps adjacent elements if they're in the wrong order. It's named because larger elements "bubble up" to the end.

You make multiple passes through the array. After each pass, the largest unsorted element reaches its correct position.

function bubbleSort(arr, n):
    for i from 0 to n - 1:
        swapped = false
        for j from 0 to n - i - 2:
            if arr[j] > arr[j + 1]:
                swap(arr[j], arr[j + 1])
                swapped = true
        if not swapped:
            break

Early termination: If no swaps occur in a pass, the array is already sorted. This gives you $O(n)$ best-case performance.

Stability: Bubble Sort is stable. Equal elements maintain their relative order because you only swap when strictly greater.

When to use: Bubble Sort is inefficient for large datasets. You should use more efficient algorithms like Merge Sort or Quick Sort for production code.

Applications: You use Bubble Sort for educational purposes, small datasets, nearly-sorted arrays, and understanding sorting fundamentals.

Time complexity: $O(n^2)$ average and worst case, $O(n)$ best case with early termination.

Space complexity: $O(1)$ because you sort in place.