# Optimized Bubble Sort

# Optimized Bubble Sort

Optimized bubble sort improves the basic version by stopping early when the array becomes sorted. During a pass, if no swaps occur, the algorithm concludes that the sequence is already ordered and terminates.

This reduces unnecessary passes, especially for nearly sorted inputs.

## Problem

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

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

## Algorithm

Track whether any swap occurs during a pass. If a full pass completes without swaps, terminate.

```id="k3d9f1"
optimized_bubble_sort(A):
    n = length(A)
    for i from 0 to n - 1:
        swapped = false
        for j from 0 to n - i - 2:
            if A[j] > A[j + 1]:
                swap(A[j], A[j + 1])
                swapped = true
        if swapped == false:
            break
```

## Example

Let

$$
A = [1, 2, 3, 5, 4]
$$

Pass 1:

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

Pass 2:

No swaps occur, so the algorithm stops early.

## Correctness

If a pass produces no swaps, then for all adjacent pairs:

$$
A[j] \le A[j+1]
$$

which implies the entire sequence is sorted. Therefore termination is correct.

## 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
* adaptive to nearly sorted input

## When to Use

Use this variant when the input may already be sorted or close to sorted. It avoids redundant passes and improves practical performance compared to the basic version.

## Implementation

```id="p4n8q2"
def optimized_bubble_sort(a):
    n = len(a)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:
            break
    return a
```

```id="z7x2m5"
func OptimizedBubbleSort[T constraints.Ordered](a []T) {
    n := len(a)
    for i := 0; i < n; i++ {
        swapped := false
        for j := 0; j < n-i-1; j++ {
            if a[j] > a[j+1] {
                a[j], a[j+1] = a[j+1], a[j]
                swapped = true
            }
        }
        if !swapped {
            break
        }
    }
}
```