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.

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

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

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
        }
    }
}