Skip to main content

DSAPath6 mincore

Bubble Sort

Bubble sort repeatedly swaps adjacent out-of-order items until the array is sorted. It is simple, stable, and usually too slow for real use.

DifficultyCore
TierTier 2
ModuleSorting Searching
LanguagesPython

Why This Matters

Bubble sort is useful as a warning label. It is easy to state and easy to analyze, but it shows why a simple local rule can waste many comparisons and swaps.

Core Idea

Repeatedly scan the array. Whenever adjacent items are out of order, swap them. After one full pass, the largest item has moved to the end.

Worked example: [3, 1, 2] becomes [1, 3, 2] after comparing 3 and 1, then [1, 2, 3] after comparing 3 and 2.

PropertyBubble sort
worst-case timeO(n2)O(n^2)
extra spaceO(1)O(1)
stableyes
production userarely

Common Mistakes

  • Using bubble sort because it is easy to remember.
  • Forgetting the early-exit optimization when no swaps occur.
  • Thinking adjacent swaps imply efficiency. They often imply too much movement.

Exercises

  • Run one pass of bubble sort on [4, 2, 1, 3].
  • Count the swaps needed for a reverse-sorted length-4 array.
  • Explain why insertion sort is usually a better simple sort.

Next Topics

References

  • Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (4th ed., 2022). Ch. 2.
  • Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed., 1998).