Skip to content

Bubble Sort Visualizer

O(n²) avgstablein-place
1/44

What is Bubble Sort?

Bubble sort is a simple comparison sort that walks through the array comparing each pair of neighbours and swapping them when they are out of order. After each pass the largest remaining element has “bubbled” to the end, so the sorted region grows from the right, and a pass with no swaps means the array is sorted. It runs in O(n²) time on average and in the worst case, O(n) on already sorted input, with O(1) extra space.

How it works

  1. Start at the left end of the unsorted part with j = 0.
  2. Compare A[j] with A[j + 1]; if A[j] > A[j + 1], swap them.
  3. Move one position right and repeat until the end of the unsorted part. The largest unsorted value is now in its final place.
  4. Shrink the unsorted part by one and start the next pass from the left.
  5. Stop as soon as a whole pass makes no swaps (or after n − 1 passes): every neighbouring pair is in order, so the array is sorted.

Worked example: sorting [38, 27, 43, 3, 9, 82, 10]

This is the array the visualizer above opens with. Watch where the largest values go:

  • Pass 1: 38 and 27 swap, 43 is carried past 3 and 9, then 82 takes over and is carried past 10: [27, 38, 3, 9, 43, 10, 82]. 6 comparisons, 4 swaps, and 82 is final.
  • Pass 2: [27, 3, 9, 38, 10, 43, 82] — 3 swaps, 43 is final.
  • Pass 3: [3, 9, 27, 10, 38, 43, 82] — 3 swaps, 38 is final.
  • Pass 4: [3, 9, 10, 27, 38, 43, 82] — 1 swap.
  • Pass 5: no swaps, so the swapped flag stops the sort one pass before the maximum of n − 1 = 6.

Total: 20 comparisons and 11 swaps. Eleven is exactly the number of inversions in the input — pairs that are in the wrong order — because each swap of two neighbours fixes exactly one inversion and nothing else.

Why bubble sort is O(n²)

In the worst case, a reversed array, every pair is an inversion. Pass 1 makes n − 1 comparisons, pass 2 makes n − 2, and so on, for n(n − 1)/2 comparisons and just as many swaps — 499,500 of each for 1,000 elements. On random input about half of all pairs are inverted, so the average is still around n²/4 swaps: quadratic.

The best case is an already sorted array. With the swapped flag, the first pass makes n − 1 comparisons, sees no swaps and stops: O(n). Without the flag bubble sort makes all n(n − 1)/2 comparisons even on sorted input, which is why textbooks sometimes disagree about its best case.

Rabbits and turtles

Large values move fast: a big value can travel the whole array in a single pass (a “rabbit”). Small values near the end move slowly, because each pass carries them only one step left (a “turtle”). In the example, 10 starts at the last index and needs four passes to reach its place.

Turtles are why bubble sort stays slow even on nearly sorted data when a small value sits near the end. Cocktail shaker sort bubbles in both directions, and comb sort compares elements a gap apart (the same idea as shell sort) — both attack exactly this problem.

Bubble sort vs insertion and selection sort

All three are O(n²), in-place and short, but they are not equally good:

  • Insertion sort also makes one move per inversion, but a shift is a single write instead of a swap, and its scan stops at the first smaller element — about half of bubble sort's comparisons on random input. Libraries use it for small arrays.
  • Selection sort makes at most n − 1 swaps, which helps when writes are expensive, but always n(n − 1)/2 comparisons, even on sorted input.
  • Bubble sort is stable and notices a sorted array in one pass, but does the most swaps of the three. Its real value is teaching passes, loop invariants and inversions.

Common mistakes and interview tips

  • Running the inner loop to n − 1 on every pass instead of n − 1 − i. It still sorts, but re-checks the finished tail.
  • Leaving out the swapped flag and still claiming an O(n) best case.
  • Writing >= instead of >: equal neighbours get swapped and the sort is no longer stable.
  • A common follow-up is “how many swaps does bubble sort make?” — the number of inversions — and then “count the inversions faster”, which a modified merge sort does in O(n log n).

Time and space complexity

CaseTimeSpaceWhy
BestO(n)O(1)Already sorted: one pass, no swaps, and the swapped flag stops it.
AverageO(n²)O(1)About n²/4 swaps — roughly half of all pairs are inverted.
WorstO(n²)O(1)Reversed input: n(n − 1)/2 comparisons and n(n − 1)/2 swaps.

Bubble Sort in Python

def bubble_sort(A):
    # Sorts list A in place, ascending. Stable, O(1) extra space.
    n = len(A)
    for i in range(n - 1):              # i = 0 .. n-2
        swapped = False
        for j in range(n - 1 - i):      # j = 0 .. n-2-i
            if A[j] > A[j + 1]:         # strict > keeps it stable
                A[j], A[j + 1] = A[j + 1], A[j]
                swapped = True
        # A[n-1-i] is now final
        if not swapped:                 # no swaps: already sorted
            break

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Is bubble sort stable?

Yes. It only swaps neighbours when the left one is strictly greater, so equal elements never pass each other. Changing > to >= would break that.

What is the best-case time complexity of bubble sort?

O(n) on an already sorted array — but only with the early-exit swapped flag. Without it, bubble sort always makes n(n − 1)/2 comparisons.

How many swaps does bubble sort make?

Exactly the number of inversions in the input, because every swap of two neighbours removes one inversion. That ranges from 0 for sorted input to n(n − 1)/2 for reversed input.

Why is it called bubble sort?

On every pass the largest remaining value rises to the end of the array, like a bubble rising to the surface.

Is bubble sort used in practice?

Rarely. Insertion sort is just as simple and faster, so real libraries use it for small arrays instead. Bubble sort survives mainly as a teaching tool.

Keep learning

Last updated