Skip to the page
Year 8 · Summer 1 · Algorithms: search and sort

Bubble sort, step by step

UnpluggedPresent ▶

What this lesson covers

Topic 12 Searching and sorting

KS3 Computing · Searching finds an item. Sorting puts items in order. Some algorithms are hugely faster than others on big lists, and the difference grows as the list grows.

Computational ThinkingCambridge Lower Secondary Computing 0860

You will learn to

  • Describe bubble sort: compare neighbours, and swap them if they are in the wrong order.
  • Carry out one full pass of bubble sort and show the list after it.
  • Explain why the biggest number reaches the end after the first pass.
  • Explain when bubble sort stops: after a pass with no swaps.

Success criteria

  • I can call the swaps for eight pupils holding numbers.
  • I can show the list after each pass, and check it with the bubble sort toy.
  • I can count the passes and the comparisons for a short list.

Key words

Say each word, then read what it means. Every one is in the glossary too.

Bubble sort
Swap neighbours until a whole pass makes no swaps.
Insertion sort
Slide each item into its place in the sorted part.
Merge sort
Split into single items, then merge back in order.
Linear search
Check every item in turn.
Binary search
Search a sorted list by halving it each step.

The explanation

Read it here, or open the study page below to go one step at a time with things to try.

Bubble sort

Bubble sort: compare neighbours, swap if they're in the wrong order. One trip along is a pass. Stop when a pass makes no swaps.

e.g.Example

[5, 1, 4, 2, 8] → pass 1 → [1, 4, 2, 5, 8] → pass 2 → [1, 2, 4, 5, 8] → pass 3: no swaps, done.

!Watch out

Easy to code, but very slow on big lists.

Insertion sort

Insertion sort: like sorting playing cards. Take the next card and slide it into the right place among the sorted ones.

e.g.Example

[5 | 1, 4, 2, 8] → [1, 5 | 4, 2, 8] → [1, 4, 5 | 2, 8] → [1, 2, 4, 5 | 8] → [1, 2, 4, 5, 8].

Merge sort

Merge sort: split the list in half again and again until every piece has 1 item. Then merge pieces back together in order.

  1. Split: [6, 3, 8, 1] [5, 2, 7, 4]
  2. Split: [6, 3] [8, 1] [5, 2] [7, 4]
  3. Split into singles.
  4. Merge: [3, 6] [1, 8] [2, 5] [4, 7]
  5. Merge: [1, 3, 6, 8] [2, 4, 5, 7]
  6. Merge: [1, 2, 3, 4, 5, 6, 7, 8]
★Remember

To merge, only compare the front item of each list and take the smaller.

Study it

Open the study page and go one step at a time.

Topic 12 · Year 8

Searching and sorting

Searching finds an item. Sorting puts items in order. Some algorithms are hugely faster than others on big lists.

The steps for this lesson

Try it

Check yourself

One question at a time. The reason shows after each answer.

Saved on this device.