Optimized Bubble Sort Visual Guide | Draftsbook

Basic Sorting · Article 2 of 62

Optimized Bubble Sort

Bubble Sort with two small but valuable improvements: an early-exit flag and a shrinking last-swap boundary. The asymptotic class doesn't change, but real inputs run dramatically faster.

How it works

The plain Bubble Sort keeps doing passes even after the array is already sorted. Two optimizations fix that:

Swapped flag. Before each pass, set swapped = false. If you complete the pass without swapping anything, the array is sorted — break out immediately.
Last-swap boundary. The position of the last swap on a pass is the new upper bound; everything to the right is already sorted, so the next pass can stop there.

The best case becomes O(n) — one clean pass over an already-sorted input — while the worst case (reversed input) is still O(n²).

Complexity

Best time

O(n)

Average time

O(n²)

Worst time

O(n²)

Extra space

O(1)

Stable

Yes

In-place

Yes

Try the Nearly sorted preset and watch the algorithm finish after just one or two passes — that is the early-exit kicking in.

Interactive visualization

Pseudocode

procedure optimizedBubbleSort(A):
  n ← length(A)
  repeat:
    lastSwap ← 0
    for j from 0 to n − 2:
      if A[j] > A[j+1]:
        swap A[j], A[j+1]
        lastSwap ← j + 1
    n ← lastSwap
  until n ≤ 1

JavaScript implementation

function optimizedBubbleSort(arr) {
  let n = arr.length;
  while (n > 1) {
    let lastSwap = 0;
    for (let j = 0; j < n - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        lastSwap = j + 1;
      }
    }
    n = lastSwap; // everything after the last swap is already sorted
  }
  return arr;
}

Pros and cons

Pros

Best case becomes O(n) — one pass detects an already-sorted array.
Last-swap boundary shrinks the working range quickly on nearly-sorted input.
Still stable and in-place.
Two-line code change over plain Bubble Sort.

Cons

Worst and average case remain O(n²).
Insertion sort outperforms it in practice even when both are O(n) on sorted data.
Adds two state variables — minor, but still moving parts.

When to use it

Streams that arrive almost in order. Best case really is linear.
Educational comparison with plain Bubble Sort, to demonstrate how a small flag changes the best-case curve.
Embedded code-golf where every extra branch matters less than tiny code size.

Up next: Selection Sort — instead of swapping every out-of-order neighbor, find the minimum once and swap it into place. Many fewer writes, same O(n²) comparisons.

Optimized Bubble Sort: Mechanism, Complexity Analysis & Interactive Visualizer