# Bubble Sort

# 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.

```id="l2k9d1"
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

```id="a9f3p2"
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
```

```id="c8m1z4"
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]
            }
        }
    }
}
```