Course contentsShow
← Computer Science
Lesson 743 of 2,87218. Sorting AlgorithmsFree lesson

Bubble Sort: Optimization

Implementing early termination when no swaps occur in a pass, and shrinking the comparison range each iteration.

Bubble Sort: Optimization

You'll learn how to make Bubble Sort faster by stopping early and reducing unnecessary comparisons.

The Core Idea

Standard Bubble Sort always runs through all passes, even when the list becomes sorted early. Two simple optimizations dramatically improve performance in practice:

  1. Early Termination: If a complete pass happens without any swaps, the list is already sorted—stop immediately.
  2. Shrinking Range: After each pass, the largest unsorted element "bubbles" to its final position at the end. You don't need to compare it again, so reduce the comparison range by one each iteration.

How It Works

Think of sorting books by height. After your first pass through the shelf, the tallest book is definitely in the rightmost spot. On your second pass, you can ignore that last position entirely—it's done. If you ever walk through the entire shelf without swapping any books, you know everything is sorted and can stop.

Early termination uses a flag (like swapped) that tracks whether any swaps occurred during a pass. No swaps means sorted.

Shrinking range means in pass 1 you compare n-1 pairs, in pass 2 you compare n-2 pairs, and so on. The inner loop's upper limit decreases each time.

These optimizations don't change the worst-case complexity (still O(n²)), but they make the best case O(n) when the array is already sorted, and significantly speed up nearly-sorted data.

Practical Impact

On a nearly-sorted list, optimized Bubble Sort can finish in just one or two passes instead of running all n passes unnecessarily.

Key Takeaway:
Bubble Sort can be optimized with early termination (stop when no swaps occur) and shrinking comparison ranges (ignore already-sorted tail elements), improving best-case performance to O(n).