Bubble Sort

Bubble sort repeatedly compares neighbouring values and swaps them when they are in the wrong order, so the largest value "bubbles" to the end on every pass.

Start

5
3
8
2
1
  • Comparing
  • Swapping
  • In final place

5 values. Bubble sort walks the list comparing neighbours, swapping any pair in the wrong order.

Step 1 / 28
Pass
0
Comparisons
0
Swaps
0
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 not swapped: stop — it is sorted

What's happening?

  1. Each pass walks the unsorted part from left to right, comparing pairs of neighbours.
  2. A pair in the wrong order swaps; after one pass the largest remaining value is at the end and never moves again.
  3. If a whole pass makes no swaps, the list is already sorted and the algorithm stops early.

Complexity

Time
O(n²) worst and average · O(n) best (already sorted)
Space
O(1) — it sorts in place

Where you'll meet it

Almost never used for real data — it exists to teach comparing, swapping and loop invariants. Libraries use merge sort, quicksort or Timsort instead.

Common mistake

Forgetting that each pass can stop one position earlier: after pass k, the last k values are already in place.

FAQ

Why is bubble sort O(n²)?

In the worst case each of about n passes compares about n pairs, so the work grows with n × n.

Is bubble sort stable?

Yes. Equal values are never swapped, so their original order is kept.

When does bubble sort finish in one pass?

When the list is already sorted: the first pass makes no swaps and the algorithm stops.