KS3 · Computer Science

Bubble sort

Imagine sorting a shuffled row of cards when you may only ever look at two neighbouring cards at a time. Could you still do it? Bubble sort can.

Computing · Algorithms

Watch the 9 bubble to the end

Bubble sort putting 9 3 7 2 into ascending order, one comparison at a time. It only ever looks at two neighbours.

Predict first: after pass 1, which number will be sitting at the end of the list?

 1  REPEAT
 2    swaps = 0
 3    FOR each pair of neighbours, left to right
 4      IF left item > right item THEN
 5        swap the two items
 6        swaps = swaps + 1
 7      ENDIF
 8    NEXT pair
 9  UNTIL swaps = 0

pass	pair	swap?	list	swaps
			9 3 7 2

Output

Step 1: Here's the list: 9 3 7 2. The goal is ascending order, smallest to largest. Keep your eye on the 9. It's the biggest, and it starts right at the front.

1 / 17

Press Next to make one comparison at a time. Watch the pair, the list column and the swaps count.

Step 1 of 17: Here's the list: 9 3 7 2. The goal is ascending order, smallest to largest. Keep your eye on the 9. It's the biggest, and it starts right at the front..

The stopping rule

When does bubble sort stop?

A bubble sort is putting a list of numbers into ascending order. It has already made at least one pass.

Which of these is closest to what you think right now?

It stops after one pass. By then every pair has been compared.It stops as soon as the list is in order.It stops when the smallest number reaches the front.It stops after a whole pass in which no swaps were made.

How sure are you?

I'm sureI think soI'm guessing

It stops after one pass. By then every pair has been compared.

This is a common misconception

One pass only makes one thing certain: the biggest number has reached the end. Everything in front of it can still be jumbled. In the 9 3 7 2 sort, after pass 1 the list read 3 7 2 9, and the 7 and the 2 were still the wrong way round. So the algorithm goes round again.

It stops as soon as the list is in order.

This is a common misconception

That's how a person would do it: you glance along the whole list and see it's finished. The algorithm can't glance. It only ever looks at two neighbours at a time. In the 9 3 7 2 sort, the list was in order by the end of pass 3, but pass 3 had made a swap, so as far as the algorithm knew, something could still be out of place. It needed pass 4 to find out.

It stops when the smallest number reaches the front.

This is a common misconception

The smallest number can be at the front while the rest are still jumbled. Try 1 4 3 2: the 1 is at the front before the sort even starts, yet the 4, 3 and 2 are in the wrong order. The algorithm has no rule about the front of the list at all.

It stops after a whole pass in which no swaps were made.

This matches the evidence

Exactly. A pass with no swaps means every pair of neighbours was checked and every pair was already the right way round. If every neighbour is in order, the whole list is in order. That swap-free pass is the algorithm's proof, and it's why the pseudocode says UNTIL swaps = 0.

Bubble sort doesn't stop when the list looks sorted. It stops when a full pass makes no swaps, because that pass is its proof.

Your turn to trace

Sort four words into alphabetical order

Use bubble sort to put kiwi, apple, pear, fig into alphabetical order (A to Z). A pair is the wrong way round when the left word comes later in the alphabet. Record the list after each step and the swaps in each pass.

Start: kiwi, apple, pear, fig. Pass 1 begins with the first pair of neighbours, kiwi and apple.
missing step

Which line is step 2?

kiwi and apple: k comes after a, so swap. List: apple, kiwi, pear, fig (1 swap so far).kiwi and apple: no swap, kiwi is already first. List: kiwi, apple, pear, fig (0 swaps).kiwi and apple: swap, and apple goes to the front for good. List: apple, fig, kiwi, pear.

Predict, then check

Both lists hold the same five numbers. The only difference is how jumbled they are.

Bubble sort puts each list into ascending order. List A is 2 1 3 4 5. List B is 5 4 3 2 1. Which one finishes in fewer passes?

Is it any good?

Weigh up bubble sort

The claim

Bubble sort is a good way to put a list in order.

Place each piece of evidence to load the balance. Mark the strong ones — they count double.

The whole idea fits in one sentence: compare neighbours, swap if they're the wrong way round, repeat until a pass makes no swaps.
Evidence 1: does it support or challenge the claim?SupportsChallenges
Strong evidence
It's short and simple to write as a program: one loop inside another and a single IF.
Evidence 2: does it support or challenge the claim?SupportsChallenges
Strong evidence
On a list that is already nearly sorted, it reaches a pass with no swaps early and stops.
Evidence 3: does it support or challenge the claim?SupportsChallenges
Strong evidence
Each pass compares every pair of neighbours. On a list of 1,000 items, that's 999 comparisons in every single pass.
Evidence 4: does it support or challenge the claim?SupportsChallenges
Strong evidence
A long, jumbled list can need many passes before it gets a pass with no swaps.
Evidence 5: does it support or challenge the claim?SupportsChallenges
Strong evidence
On a long, jumbled list it can make a very large number of swaps, and every swap takes time.
Evidence 6: does it support or challenge the claim?SupportsChallenges
Strong evidence

WHAT YOU'VE LEARNED

A quick recap of today's lesson.

Look at two neighbours. Swap them if they're the wrong way round. Move along one place. That tiny rule, repeated pass after pass, sorts a whole list.

What you need to know

A sorting algorithm puts the items in a list into order: ascending (smallest to largest), descending (largest to smallest) or alphabetical.
Bubble sort compares adjacent (neighbouring) pairs, starting at the beginning of the list, swaps a pair if it is in the wrong order, then moves on one place to the next pair.
One complete run through the list from start to end is a pass. After each pass, the largest unsorted item has bubbled to its place at the end of the unsorted part.
Bubble sort repeats passes until a pass makes no swaps. A pass with no swaps shows the list is sorted, so the algorithm stops.
To trace a bubble sort by hand, write the list after each comparison or each pass, and record the swaps made.
Bubble sort is simple to understand and write, but slow (inefficient) for long lists. It is quicker when the list is nearly sorted.

The big picture

A sorting algorithm puts a list into order: ascending, descending or alphabetical. Bubble sort compares neighbouring pairs from the start of the list, swaps any pair that is the wrong way round, and moves on one place. One run through the list is a pass, and each pass carries the largest unsorted item to the end of the unsorted part. Bubble sort keeps making passes until a pass makes no swaps, which shows the list is sorted. It is simple to understand and write, but slow for long lists; it is quicker when the list is nearly sorted.

Key points

1Compare two neighbours, swap them if they're the wrong way round, then move on one place.

2'Wrong way round' depends on the order you want: for ascending, the left item is bigger; for descending, the left item is smaller; for alphabetical, the left word comes later in the alphabet.

3A pass is one run from the start of the list to the end. Each pass settles the biggest unsorted item at the end of the unsorted part.

4The algorithm stops only after a pass with no swaps, even if the list already looks sorted.

5Record a trace as the list after each comparison or pass, plus the number of swaps.

6Simple to write, slow on long lists, quicker on nearly sorted lists.

.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 bubble sort to put 4, 8, 1, 6 into descending order (largest first). Write the list after each pass and the number of swaps in each pass, and say when the algorithm stops.

⚠ Watch out

Forgetting that the list has changed after a swap. After swapping, the next comparison is between the item that has just moved and its new neighbour, not the pair from the original list.

🧠

Memory hook

Two neighbours, wrong way round? Swap them and step along. Pass after pass the big ones bubble to the end, and the first pass with zero swaps says STOP.

✓

Check yourself

Bubble sort 7, 2, 5 into ascending order, writing the list and the swaps after each pass. How many passes does it make, and why not stop after pass 1?

Flashcards

(13)

What does a sorting algorithm do?

It puts the items in a list into order, for example numbers into ascending or descending order, or words into alphabetical order.

Ascending or descending: which is smallest to largest?

Ascending is smallest to largest. Descending is largest to smallest.

What is the basic move in bubble sort?

Compare two neighbouring (adjacent) items, swap them if they're in the wrong order, then move on one place to the next pair.

What is a pass?

One complete run through the list, from the start to the end, comparing each pair of neighbours.

In an ascending bubble sort, what is certain after each pass?

The largest unsorted item has bubbled to its correct place at the end of the unsorted part of the list.

When does bubble sort stop?

After a pass in which no swaps were made.

Why can't bubble sort stop as soon as the list looks sorted?

It only ever looks at two neighbours at a time, so it can't see the whole list. It needs a pass with no swaps as proof that every pair is in order.

Sorting into descending order: when do two neighbours get swapped?

When the left item is smaller than the right one.

Sorting words alphabetically: when do two neighbours get swapped?

When the left word comes later in the alphabet than the right word.

How do you record a bubble sort traced by hand?

Write the list after each comparison or after each pass, and record the swaps made.

Give one strength of bubble sort.

It is simple to understand and simple to write.

Why is bubble sort slow on a long list?

It may need many passes, and each pass compares every pair, so it can make very many comparisons and swaps.

When is bubble sort quicker?

When the list is already nearly sorted, because it reaches a pass with no swaps early.

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

Watch the 9 bubble to the end

When does bubble sort stop?

Sort four words into alphabetical order

Weigh up bubble sort

More KS3 Computer Science topics