- Compared
- Swapped
- In place
Bubble sort
Bubble sort walks through a list again and again, compares each pair of neighbours, and swaps them when the left one is larger. After every pass the largest value still out of place has bubbled to the end. Play the sort at any speed, or step through it one comparison at a time, and watch the counters for comparisons, swaps, and passes. Press Play to watch the sort, or Step and Back to go one comparison at a time. Drag the step slider to jump anywhere. The tiles count comparisons, swaps and passes. Choose how many bars, how they start, or type your own numbers. With the board selected, the arrow keys step, the space bar plays and pauses, and Home and End jump to the start and the end.
How it works
- Choose how many bars and how they start: random, nearly sorted, reversed, or with few unique values. Or type your own numbers.
- Press Play, or use Step and Back to move one comparison at a time. Drag the step slider to jump anywhere in the sort.
- Watch the tiles count comparisons, swaps, and passes, and compare them with the worst case.
How bubble sort works
Start at the left. Compare the first two values; if the left one is larger, swap them. Move one place to the right and compare again, up to the end of the list. That is one pass, and it leaves the largest value in the last place. The next pass stops one place earlier. Keep going until a pass makes no swaps, or until only one value is left.
Counting the work
For n values, the first pass makes n − 1 comparisons, the next n − 2, and so on, so a full sort makes at most n(n − 1)/2 comparisons. The number of swaps is always the number of inversions in the start list: pairs of values that are in the wrong order. A reversed list has the most, n(n − 1)/2. A sorted list has none, and with the early stop it takes a single pass of n − 1 comparisons.
Frequently asked questions
Why is it called bubble sort?
Because large values rise to the end of the list like bubbles in water. In each pass the largest value not yet in place moves step by step to the right until it reaches its final place.
How many comparisons and swaps does bubble sort make?
At most n(n − 1)/2 comparisons for n values: 45 for 10 values, 780 for 40. The swaps always equal the number of inversions in the start list, from none for a sorted list to n(n − 1)/2 for a reversed one.
What does the early stop do?
If a whole pass makes no swaps, every pair of neighbours is in order, so the list is sorted and the sort can stop. With the early stop on, a sorted list takes one pass. With it off, bubble sort always makes all n − 1 passes.
Is bubble sort used in practice?
Rarely. It is simple and stable, but it takes time proportional to n² on average. Insertion sort does the same job with fewer steps on small or nearly sorted lists, and merge sort or quicksort are much faster on large ones.
Are my numbers sent anywhere?
No. The sort runs in your browser, and your last settings stay in this browser's local storage.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Go to Editor