Bubble Sort

Bubble sort is a simple comparison-based sorting algorithm. It repeatedly scans the sequence and swaps adjacent elements when they are in the wrong order. After each pass, the largest unsorted element moves to its correct position at the end.

The name comes from the way larger elements gradually “bubble up” toward the right side.

Problem

Given a sequence $A$ of length $n$ , reorder it such that:

A[0] \le A[1] \le \cdots \le A[n-1]

Algorithm

Perform multiple passes over the array. During each pass, compare adjacent pairs and swap them if needed.

bubble_sort(A):
    n = length(A)
    for i from 0 to n - 1:
        for j from 0 to n - i - 2:
            if A[j] > A[j + 1]:
                swap(A[j], A[j + 1])

Example

Let

A = [5, 1, 4, 2]

Pass 1:

pair	action	result
(5,1)	swap	[1,5,4,2]
(5,4)	swap	[1,4,5,2]
(5,2)	swap	[1,4,2,5]

Pass 2:

pair	action	result
(1,4)	keep	[1,4,2,5]
(4,2)	swap	[1,2,4,5]

Pass 3:

pair	action	result
(1,2)	keep	[1,2,4,5]

Sorted result:

[1, 2, 4, 5]

Correctness

Each pass ensures that the largest remaining unsorted element moves to its correct position at the end. After $k$ passes, the last $k$ elements are fixed. After $n-1$ passes, all elements are in sorted order.

Complexity

case	comparisons	time
best (already sorted)	$n$	$O(n)$
worst	$\frac{n(n-1)}{2}$	$O(n^2)$
average	$\approx \frac{n^2}{2}$	$O(n^2)$

Space complexity:

O(1)

Properties

stable
in-place
simple to implement
inefficient for large datasets

When to Use

Bubble sort is mainly useful for teaching and small inputs. It can also be used when the array is almost sorted and combined with an early-exit optimization.

Implementation

def bubble_sort(a):
    n = len(a)
    for i in range(n):
        for j in range(0, n - i - 1):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
    return a

func BubbleSort[T constraints.Ordered](a []T) {
    n := len(a)
    for i := 0; i < n; i++ {
        for j := 0; j < n-i-1; j++ {
            if a[j] > a[j+1] {
                a[j], a[j+1] = a[j+1], a[j]
            }
        }
    }
}