AlgoVerse

Bubble sort

Compare neighbouring pairs and swap them when needed; in each pass the largest item bubbles up to the end.

In each pass, neighbouring pairs are compared from left to right and swapped when they are in the wrong order. The largest item of the unsorted part bubbles up to its end and lands in its final place. So each pass is one position shorter than the last.

Read the full explanation ↓
Input:
n=6PDF export

Six mixed numbers; a few passes are needed for all the bubbles to rise.

  1. def bubble_sort(a):
  2. n = len(a)
  3. for end in range(n - 1, 0, -1):
  4. swapped = False
  5. for i in range(end):
  6. if a[i] > a[i + 1]:
  7. a[i], a[i + 1] = a[i + 1], a[i]
  8. swapped = True
  9. if not swapped:
  10. break
  11. return a

Invariant: After each pass, a[end..n−1] holds the largest items in their final places.

Start

501142238435

Local variables

Orange = changed in this step

a list

514283

Call stack

  1. bubble_sort()line 1
Step 1 of 62
Black = pass_start · Orange = key stepcompare: 0/14 · swap: 0/7 · pass_start: 0/4 · early_exit: 0/1

    How the work grows with input size

    Average of 12 random graphs per n (fixed seeds). Hollow marker = the input on screen.

    • comparisons
    • swaps
    • current input (n=6)
    05010015046810121416n = number of itemscomparisonsswaps
    Show as a table
    ncomparisonsswaps
    45.73.3
    613.67.6
    824.812
    1042.621.3
    1261.329.4
    1484.943
    1611258.4
    Explanation

    The idea

    In each pass, neighbouring pairs are compared from left to right and swapped when they are in the wrong order. The largest item of the unsorted part bubbles up to its end and lands in its final place. So each pass is one position shorter than the last.

    Stopping early

    If a pass makes no swap, the array is sorted and going on is pointless. With this trick a sorted input needs only one pass (n − 1 comparisons).

    Cost

    • O(n²) in the worst and average case, O(n) in the best case.
    • Extra memory O(1); the sort is stable, because only neighbours are swapped and only when they are >.

    "Rabbits and turtles"

    A large item at the front (a rabbit) runs to the end in one pass, but a small item at the end (a turtle) moves only one place forward per pass. The "turtle" input shows this.

    What to watch in the trace

    • The end arrow is the border of the unsorted part; bars after it are in their final places.
    • Compare the number of swap steps with the number of out-of-order pairs (inversions): they are exactly equal.