GCSE · Computer Science · Edexcel · Spec 1CP2

Bubble sort

Look at two neighbours, swap them if they're the wrong way round, repeat. Watch the biggest item and you'll see it rise to the end like a bubble.

Algorithms · Sorting

One pass, one comparison at a time

Eight playing cards, and the ace is low, so it counts as 1. Step through a single pass into ascending order and keep your eye on the card that gets carried along.

Before you press Next: the first two cards are 6 and 4. Swap or no swap?

 1  take the list of items to be sorted
 2  go to the next item (at the start, the first item)
 3  compare it with the item next to it
 4  IF this item > next item THEN swap the two items
 5  repeat until the last item in the list is reached

Variables

list=6 4 5 2 8 A 7 3swap?=—swaps=0comparing=—comparisons=0

Output

Step 1: Eight cards in no particular order. This pass will walk along the row once, looking at just two neighbours at a time.

1 / 9

Press Next one comparison at a time. Before each step, say out loud whether the pair will swap.

Step 1 of 9: Eight cards in no particular order. This pass will walk along the row once, looking at just two neighbours at a time..

Exam line: One pass carries the largest item to the end of the list. That item is now in its final place, but nothing else is guaranteed yet.

Counting comparisons

How many comparisons does one pass make?

Nine cups in a row, labelled 43, 21, 2, 50, 3, 80, 35, 64, 7. How many comparisons will one full pass of bubble sort make? Commit to a number before you count.

Your estimate

6 comparisons

Nine cups in a row, labelled 43, 21, 2, 50, 3, 80, 35, 64, 7. How many comparisons will one full pass of bubble sort make? Commit to a number before you count. Estimate between 0 comparisons and 12 comparisons.

0 comparisons12 comparisons

When does it stop?

When is the sort finished?

You're partway through a bubble sort. So far, every pass has made at least one swap.

Which is closest to what you think right now? The sort can stop…

…after the first pass, because that pass puts everything in order.…the moment it makes its last swap.…as soon as the list looks sorted to me.…after it completes a whole pass that makes no swaps.

How sure are you?

I'm sureI think soI'm guessing

…after the first pass, because that pass puts everything in order.

This is a common misconception

A pass only promises one thing: the largest item reaches the end. Think back to the cards. After pass 1 the 8 was home, but 4 5 2 6 A 7 3 was still a mess. A first pass might happen to sort a list, but you can never count on it.

…the moment it makes its last swap.

This is a common misconception

Here's the catch: you can only know a swap was the last one by checking everything after it. The algorithm can't see ahead. So it keeps going, and it only knows it's finished when a whole pass goes by with no swaps.

…as soon as the list looks sorted to me.

This is a common misconception

You can see the whole list at a glance, but the algorithm can't. It only ever looks at two neighbours at a time, so its only evidence that the list is in order is a pass in which nothing needed swapping. Even a list that's already sorted still needs that one confirming pass.

…after it completes a whole pass that makes no swaps.

This matches the evidence

Exactly. If no pair needed swapping, every item is already in front of a bigger (or equal) neighbour, so no items are out of order. That quiet pass isn't wasted: it's the proof that the list is sorted.

Keep making passes until a whole pass makes no swaps, then stop. The algorithm never stops on the last swap.

Your turn

A whole sort, pass by pass

Use a bubble sort to put these cuisines into alphabetical order: Persian, Greek, Indian, Thai, Nigerian, Italian, Spanish.

Start: Persian, Greek, Indian, Thai, Nigerian, Italian, SpanishAlphabetical order works like numbers: a word that comes later in the alphabet counts as 'bigger'.
After pass 1: Greek, Indian, Persian, Nigerian, Italian, Spanish, ThaiThai comes last alphabetically, so it's carried all the way to the end, just like the 8 card.
missing step

Which line is step 3?

After pass 2: Greek, Indian, Nigerian, Italian, Persian, Spanish, ThaiAfter pass 2: Greek, Indian, Italian, Nigerian, Persian, Spanish, ThaiAfter pass 2: Greek, Indian, Nigerian, Persian, Italian, Spanish, ThaiAfter pass 2: Greek, Indian, Persian, Italian, Nigerian, Spanish, Thai

Exam line: When you show a bubble sort, write the list out after every pass, and include the final pass that makes no swaps.

Making bubble sort faster

Bubble sort with no shortcutsvsImproved bubble sort

The stop-after-a-quiet-pass rule you've just used is one of the two ways to make bubble sort more efficient. Here's what each change saves.

Focus

After a pass with no swaps

Bubble sort with no shortcuts

Carries on making more passes anyway

Improved bubble sort

Stops straight away

The insight

Once a pass makes no swaps, nothing is out of order, so every pass after it is wasted work. Stopping there is the first improvement.

Comparisons on each pass (8 items)

Bubble sort with no shortcuts

7, 7, 7, …: every pair, every time

Improved bubble sort

7, 6, 5, …: one fewer each pass

First three passes on 8 items

Bubble sort with no shortcuts

7 + 7 + 7 = 21 comparisons

Improved bubble sort

7 + 6 + 5 = 18 comparisons

The final sorted list

Bubble sort with no shortcuts

Correct

Improved bubble sort

Exactly the same

Put it in writing

Is bubble sort the right tool?

An online shop needs to sort a list of 50,000 product names. Explain why bubble sort may be a poor choice, and give two other factors that affect which sorting algorithm to choose. [4 marks]

Your answer

0 words · your answer stays on this page and is not sent anywhere.

The mark scheme

Bubble sort is one of the slowest sorting algorithms / performs poorly on large amounts of data. (1 mark)
It makes pass after pass, and each pass compares neighbouring pairs all the way along the list, so a long list means a huge number of comparisons. (1 mark)
One other factor, e.g. how easy the algorithm is to implement and test. (1 mark)
A second, different factor, e.g. how much memory the algorithm needs, or how the data is formatted. (1 mark)

Model answer

Bubble sort is one of the slowest sorting algorithms and performs poorly on large amounts of data. It has to make pass after pass through the list, and every pass compares neighbouring pairs from one end to the other, so with 50,000 names that adds up to an enormous number of comparisons. Other factors to consider are how easy the algorithm is to implement and test, and how much memory it needs.

Say why bubble sort struggles (lots of passes, each checking every pair), not just that it's slow. Then name factors beyond speed.

WHAT YOU'VE LEARNED

A quick recap of today's lesson.

Compare two neighbours. Swap if they're the wrong way round. Repeat until a whole pass makes no swaps.

What you need to know

Bubble sort compares adjacent (neighbouring) items and swaps them if they're in the wrong order.
One complete run through the list is a pass; a full pass over n items makes n − 1 comparisons.
After each pass the largest remaining item is in its final place, but the rest of the list may still be out of order.
The sort only stops after a whole pass that makes no swaps.

The big picture

A sorting algorithm puts the items in a list into order, for example from lowest to highest. Bubble sort does it by going through the list comparing each pair of neighbouring items and swapping any pair that's out of order. One complete run through the list is called a pass, and each pass carries the largest remaining item to the end. The sort keeps making passes until a whole pass makes no swaps. It works on words as well as numbers, but it's one of the slowest ways to sort a large amount of data.

Key points

1A sorting algorithm arranges items in order; bubble sort does it by comparing neighbouring items and swapping any pair in the wrong order.

2Each complete traversal of the list is a pass. A full pass over n items makes n − 1 comparisons, one for each adjacent pair.

3After a pass, the largest remaining item is in its final position, because it wins every comparison once the pass reaches it.

4The algorithm stops only after a pass with no swaps. It never stops on the last swap.

5Efficiency improvements: stop once a pass makes no swaps, and check one fewer pair on each pass. Even so, bubble sort is slow on large data sets.

.we-_R_18slubsnpfiv5ubrb_ [data-we-step]{display:flex !important}.we-_R_18slubsnpfiv5ubrb_ [data-we-solution]{display:block !important}.we-_R_18slubsnpfiv5ubrb_ [data-we-reveal]{display:none !important}

Worked example

Problem

Use a bubble sort to put 5, 1, 4, 2 into ascending order. Write the list after each pass.

⚠ Watch out

Stopping as soon as the list looks sorted, or straight after the last swap. Bubble sort only stops after a whole pass with no swaps. Leave that final quiet pass out of your working and your answer is incomplete.

🧠

Memory hook

Biggest bubbles up; quiet pass means done. Each pass carries the heaviest hitter to the end, and only a pass with zero swaps lets you stop.

✓

Check yourself

Without scrolling up: do one pass on 9, 4, 7, 2. How many comparisons, how many swaps, which number is now fixed, and why isn't the sort finished?

Flashcards

(15)

What does a sorting algorithm do?

It arranges the items in a list into a particular order, for example lowest to highest.

Bubble sort in one sentence

Repeatedly go through the list, comparing adjacent items and swapping any pair that's in the wrong order.

What is a 'pass' in bubble sort?

One complete traversal of the list, comparing each adjacent pair in turn.

Swap rule when sorting into ascending order

If the item at the current position is greater than the one next to it, swap the two items.

Comparisons in one full pass over n items

n − 1: one for each pair of neighbours, not one per item.

Comparisons vs swaps: are they the same count?

No. Every adjacent pair is compared, but only the out-of-order pairs are swapped.

Where is the largest item after the first pass?

In its final place at the end: once the pass reaches it, it wins every comparison and is carried along.

Is a list always sorted after one pass?

No. Only the largest item is guaranteed to be in place; the rest may still be out of order.

When does bubble sort stop?

After a complete pass in which no swaps are made.

Why can't bubble sort stop on its last swap?

It only compares neighbours, so it can't know a swap was the last until a whole pass confirms nothing is out of order.

Two ways to make bubble sort more efficient

Stop as soon as a pass makes no swaps, and check one fewer pair on each pass.

Why can each later pass check one fewer pair?

Each pass fixes the next-largest item at the end, so the last pair checked is already in order.

Can bubble sort sort words?

Yes: it sorts text alphabetically in exactly the same way as numbers.

How does bubble sort cope with large data sets?

Badly. It's one of the slowest sorting algorithms and performs poorly on large collections of data.

Factors when choosing a sorting algorithm

Efficiency on large data sets, how easy it is to implement and test, how much memory it needs, and how the data is formatted.

Tap any card to flip it, or use Study as deck to go through them one at a time. In the full lesson these run as a spaced-repetition deck — you rate each card Hard, Good or Easy and the tricky ones keep coming back until they stick.

Learning with Lightbulb is opening soon

You can use this lesson now. Join the waitlist and we'll let you know when the full Lightbulb experience is ready.

Keep me posted

One pass, one comparison at a time

How many comparisons does one pass make?

When is the sort finished?

A whole sort, pass by pass

Is bubble sort the right tool?

More Edexcel GCSE Computer Science topics