Optimizations

While bubble sort will never be the fastest, we can make it better.

Early Termination

Stop early if no swaps occur in a pass:

Performance Improvement

Without optimization:

• Already sorted array: Still does n-1 passes
• Best case: O(n²)

With optimization:

• Already sorted array: Only 1 pass needed
• Best case: O(n)

When It Helps

Early termination helps most when:

• Array is already sorted or nearly sorted
• Array becomes sorted partway through
• Many elements are already in place

When It Doesn’t Help

The optimization doesn’t help when:

• Array is in reverse order
• Array is completely random
• Worst case scenarios

Cocktail Shaker Sort

A variation that sorts in both directions:

This can be slightly faster but still O(n²) worst case.

Key Takeaway

Optimizations help, but bubble sort remains O(n²) in most cases. For production code, use better algorithms like quicksort or mergesort.

What’s Next?

Let’s test your understanding with practice problems and a quiz.