cf.completefrontend
SORTING · FOUNDATION

Bubble sort

Sort a list by walking through it again and again, swapping any two neighbors that are in the wrong order.

Time O(n²)Space O(1)2 practice problemsStep-through picture

The idea

Bubble sort is the simplest sorting idea. Walk along the list and compare each item with the one right after it. If the left one is bigger, swap them. When you reach the end, the biggest item has been carried all the way to the last spot, like a bubble rising to the top of a glass.

Then do it again, but stop one spot earlier, because the last item is already in place. Each walk (called a pass) puts one more big item in its final spot at the end. After enough passes, the whole list is sorted.

Bubble sort is slow on big lists, so real code almost never uses it. It is worth learning because it shows the core moves of sorting, compare and swap, and because its number of swaps measures exactly how unsorted a list is.

An everyday example

Lining up kids by height, one pair at a time

A teacher lines up kids by height, but she may only look at two kids standing next to each other. She walks down the line. Whenever a taller kid stands just before a shorter one, she tells them to swap. By the end of her first walk, the tallest kid has been passed along to the very end. She walks the line again for the next tallest, and stops walking as soon as a full walk needs no swaps at all.

How the example maps to the code
In the exampleIn the code
One walk down the lineOne pass of the outer loop
Looking at two kids side by sideitems[i] > items[i + 1]
Telling them to swap places[items[i], items[i + 1]] = [items[i + 1], items[i]]
The tallest kid reaching the enditems[end] is final after the pass
A walk with no swaps: doneif (!swapped) break

From the slow way to bubble sort

  1. Start with the most basic question you can ask about a list: is it sorted? To answer it, you look at each pair of neighbors, items[0] and items[1], then items[1] and items[2], and so on. If every pair is in order, the whole list is in order. That check costs n - 1 comparisons.
  2. Now turn the check into a fix. Whenever a pair is in the wrong order, swap the two items right away and keep walking. One walk does not sort the list, but it does something useful: the biggest item, once the walk reaches it, wins every comparison after that and gets carried all the way to the last index.
  3. So after one walk the last item is final, and the next walk can stop one step earlier. Keep a number end for the last index that may still be wrong, and lower it by one after each walk. With n items, n - 1 walks are always enough, because each walk fixes one more item at the end.
  4. One more fact saves a lot of work. If a whole walk makes no swap, every neighbor pair is in order, which is exactly the "is it sorted?" check from the first paragraph. So track a flag swapped and stop as soon as a walk leaves it false. A walk over the unsorted part, a shrinking end, and an early stop when nothing moved: that loop is bubble sort.

How it works

  1. Set end to the last index. Everything after end is already sorted.
  2. Walk i from 0 up to end - 1, comparing items[i] with items[i + 1].
  3. If items[i] is bigger, swap the two and remember that a swap happened (swapped = true).
  4. After the walk, the biggest item in 0..end sits at end. Move end one step left.
  5. If a whole pass made no swap, the list is sorted, so stop early.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function bubbleSort(items) {
  2. for (let end = items.length - 1; end > 0; end--) {
  3. let swapped = false;
  4. for (let i = 0; i < end; i++) {
  5. if (items[i] > items[i + 1]) {
  6. [items[i], items[i + 1]] = [items[i + 1], items[i]];
  7. swapped = true;
  8. }
  9. }
  10. if (!swapped) break;
  11. }
  12. return items;
  13. }

How fast it is

TimeO(n²)
Extra memoryO(1)

Up to n - 1 passes, each comparing up to n - 1 neighbor pairs. It only swaps items inside the array, so no extra memory grows with n.

  • Best caseO(n)

    The list is already sorted, like [2, 5, 8, 13]. The first pass makes n - 1 comparisons and no swaps, and break stops the loop.

  • Average caseO(n²)

    A list in random order has about n² / 4 out-of-order pairs, and each swap fixes only one of them, so the work is still about n² divided by a small number.

  • Worst caseO(n²)

    A list in reverse order, like [9, 7, 5, 3]. Every comparison swaps: n × (n - 1) / 2 of each, which is 499,500 for 1,000 items.

Common mistakes

  • Looping i up to end instead of end - 1, so items[i + 1] reads past the unsorted part, or past the array on the first pass.
  • Forgetting to shrink the range each pass. It still sorts, but every pass rechecks the sorted tail for nothing.
  • Leaving out the swapped check. Then even a sorted list costs O(n²).
  • Using >= in the comparison. Equal items get swapped, which wastes work and breaks stability (equal items should keep their original order).

When to use it

Look for these clues in a problem:

  • The task is to understand or count swaps of neighboring items, such as "how many adjacent swaps sort this list?".
  • The list is tiny or already almost sorted, and the simplest possible code matters more than speed.
  • The question asks for the state of the list after some number of passes.

Check yourself

Answer each one in your head first, then open it.

Why can the inner loop stop at end - 1 instead of the last index?

Every item after end is already one of the biggest items in its final place. Comparing them again can never cause a swap.

How many swaps does bubble sort make on [3, 1, 2]?

Two, because the list has two inversions: (3, 1) and (3, 2). Each swap fixes exactly one.

Why is the best case O(n) only with the swapped flag?

Without it, the loops always run every pass, about n² / 2 comparisons, even on a sorted list. The flag lets the first pass notice that nothing moved and stop.

What breaks if the comparison is >= instead of >?

Equal neighbors get swapped. The list still ends sorted, but equal items change order, so the sort is no longer stable, and it does extra swaps.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 2 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps one rule, true at the top of every pass: the items after index end are the biggest items of the list, in sorted order, and they never move again. At the start, end is the last index, so the rule talks about an empty part and is true.

One pass keeps the rule. As i walks from 0 to end - 1, the biggest item seen so far always ends up at items[i + 1]: if it was at i, it is bigger than its neighbor and swaps right; if the neighbor is bigger, the neighbor is now the biggest seen. So when the walk ends, the biggest item of items[0..end] sits at end. Lowering end by one grows the sorted, final part by one item.

The loop ends because end drops by one each pass and stops at 0, so there are at most n - 1 passes. When it ends that way, the rule covers every index except 0, and the one item left must be the smallest. When it ends early, a full pass found every neighbor pair in order. A list where every neighbor pair is in order is sorted, so both endings give a sorted list.

Swaps only ever exchange two neighbors that are out of order. That fixes exactly one out-of-order pair (an inversion) and creates none, which is why the number of swaps equals the number of inversions, and why equal items never pass each other. The strict > comparison makes the sort stable.

Going deeper

3 more ideas

Why each pass fixes the biggest item

During a pass, the biggest item seen so far is always carried along: once the walk reaches it, it is bigger than its right neighbor, so it swaps right, then again, and again, until it reaches end. So after pass 1 the biggest item is last, after pass 2 the second biggest is second to last, and so on. After n - 1 passes every item is in place.

Swaps count the out-of-order pairs

A pair of positions i < j with items[i] > items[j] is called an inversion. Each swap of two neighbors fixes exactly one inversion and creates none. So bubble sort makes exactly as many swaps as the list has inversions. In [5, 1, 4, 2, 8] the inversions are (5, 1), (5, 4), (5, 2), and (4, 2): 4 of them, matching the 4 swaps.

How long it takes

In the worst case, a list in reverse order, pass 1 makes n - 1 comparisons, pass 2 makes n - 2, and so on, about n² / 2 in total. That is O(n²): 1,000 items need about 500,000 comparisons. With the early stop, a list that is already sorted needs just one pass, O(n).

Work it by hand

Every step in a table, with why

Sort 6 numbers. The list is sorted after the second pass, but the code needs a third pass with no swaps to know it.

items = [4, 1, 7, 3, 9, 8]

StependiPairswappeditems afterWhat happensWhy
1504, 1true[1, 4, 7, 3, 9, 8]4 > 1: swapThe first pass starts. 4 and 1 are in the wrong order, so they swap and swapped becomes true.
2514, 7true[1, 4, 7, 3, 9, 8]In order: keep4 is smaller than 7, so nothing moves. swapped stays true from the first swap.
3527, 3true[1, 4, 3, 7, 9, 8]7 > 3: swap7 moves one step right. It will stop at the next pair, because 9 is bigger.
4537, 9true[1, 4, 3, 7, 9, 8]In order: keepNow 9 is the biggest item seen so far, and it is the one that gets carried.
5549, 8true[1, 4, 3, 7, 8, 9]9 > 8: swap9 reaches index 5. It is final, so the next pass stops one index earlier.
6401, 4false[1, 4, 3, 7, 8, 9]In order: keepPass 2 starts with end = 4 and swapped reset to false.
7414, 3true[1, 3, 4, 7, 8, 9]4 > 3: swapThe last out-of-order pair is fixed. The list is now sorted, but the code can't know that yet.
8424, 7true[1, 3, 4, 7, 8, 9]In order: keepNothing to do.
9437, 8true[1, 3, 4, 7, 8, 9]In order: keepPass 2 ends with swapped = true, so another pass is needed.
10301, 3false[1, 3, 4, 7, 8, 9]In order: keepPass 3 starts with end = 3.
11313, 4false[1, 3, 4, 7, 8, 9]In order: keepStill no swap.
12324, 7false[1, 3, 4, 7, 8, 9]No swap all pass: breakThe whole pass made no swap, so if (!swapped) break ends the outer loop.

It returns [1, 3, 4, 7, 8, 9] after 3 passes, 12 comparisons, and 4 swaps. The list had exactly 4 out-of-order pairs: (4, 1), (4, 3), (7, 3), and (9, 8). Without the early stop it would have made 15 comparisons.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Bubble sortO(n²)O(1)Teaching, tiny lists, or when you need the exact sequence of neighbor swaps, as in an animation.
Insertion sortO(n²)O(1)Small or nearly sorted lists in real code. It does the same number of moves but with shifts, which are cheaper than swaps, and it fixes turtles in one step.
Merge sortO(n log n)O(n)Large lists where you also need stability. It is far faster than bubble sort beyond a few dozen items.
Built-in sort with a comparatorO(n log n)O(n)Almost always, in production JavaScript. It is stable and fast on partly sorted data.

Extra memory: O(1): the sort only uses end, i, and swapped, and swaps items inside the array it was given. The returned array is the same array.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Bubble sort and the other approaches, on a scale where each line up is 10 times more steps.
  • Bubble sort, Insertion sort O(n²)
  • Merge sort, Built-in sort with a comparator O(n log n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Bubble sort1001 million1 trillion
Insertion sort1001 million1 trillion
Merge sort339,96620 million
Built-in sort with a comparator339,96620 million

Inputs that need care

5 tricky inputs
An empty list [] or one item [6]
end starts at -1 or 0, so end > 0 is false at once and the list is returned untouched.
All equal items: [5, 5, 5, 5]
5 > 5 is false for every pair, so the first pass makes no swap and the loop stops after 3 comparisons.
A small item at the far end: [2, 3, 4, 5, 6, 1]
The 1 moves left only one step per pass, so the code needs all 5 passes and 15 comparisons, even though only one item is out of place. Small items moving slowly like this are called turtles.
A big item at the front: [6, 1, 2, 3, 4, 5]
The 6 is carried to the end in the first pass. The second pass makes no swap and stops: 2 passes, 9 comparisons. Big items move fast, so they are called rabbits.
Equal items with labels, like two tasks both with priority 2
The comparison is strict (>), so equal items are never swapped and keep their original order. Changing it to >= would swap them and break stability.

Variations and follow-ups

Twists interviewers add

Cocktail shaker sort

Walk left to right, then right to left, then left to right again. The backward walk carries the smallest item to the front in one pass, so turtles like the 1 in [2, 3, 4, 5, 6, 1] are fixed in one backward walk instead of five forward ones. It is still O(n²) in the worst case.

Remember the last swap

Instead of lowering end by exactly one, set it to the index of the last swap in the pass. Everything after that swap was already in order, so the next pass can skip it. On lists with a long sorted tail this skips many comparisons.

Odd-even sort

Compare all pairs that start at even indexes, then all pairs that start at odd indexes, and repeat. The pairs in one round don't overlap, so they can be compared at the same time on parallel hardware. It needs at most n rounds.

Count the swaps instead of sorting

A frequent follow-up asks for the number of neighbor swaps needed to sort a list. That number equals the inversion count, which you can get in O(n log n) with merge sort instead of running bubble sort.

In an interview

Spot it, explain it, answer follow-ups
  • You will rarely be asked to use bubble sort for speed. It shows up when a question talks about "adjacent swaps", "neighbors", or "the state after k passes". Recognize that the answer is about inversions, not about sorting fast.
  • Explain it out loud as a rule: "after each pass, the biggest unsorted item is in its final place at end". Then say why the swapped flag gives the O(n) best case.
  • Test by hand with an already sorted list (one pass, no swaps), a reversed list (every comparison swaps), and a list with a turtle like [2, 3, 1], which shows why one pass is not enough.
  • The usual follow-up is "is it stable, and why?". Yes: it only swaps neighbors that are strictly out of order, so equal items never cross.

Where frontend code uses it

The same idea in real UI code
  • Drag-to-reorder lists often move an item one slot at a time as you drag it past each neighbor, which is the same neighbor swap bubble sort makes.
  • Sorting visualizers and teaching demos use bubble sort because every step is one easy-to-draw compare or swap.
  • The number of bubble sort swaps equals the number of out-of-order pairs, a simple way to score how far a user's drag-and-drop ordering is from the correct one.

Related algorithms