Year 8 · Summer 1

Algorithms: search and sort · Lesson 2 of 5

Bubble sort, step by step

UnpluggedTopic 12 Searching and sorting

Year 8 · Algorithms: search and sort · Lesson 2 of 5

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.

Year 8 · Algorithms: search and sort · Lesson 2 of 5

Success criteria

You have got it when you can say:

  • 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.

Year 8 · Algorithms: search and sort · Lesson 2 of 5

Retrieval starter

Questions from before. Write your answers, then show them.

  1. Last lesson

    Bubble sort compares…

    A The first and last itemsB Random pairsC Neighbours

    C. Neighbours

  2. Last unit

    A program runs with no message but says the average of 4 and 6 is 7. This is a…

    A Logic errorB Runtime errorC Syntax error

    A. Logic error

  3. Earlier this year

    In UTF-8, how many bytes does ñ (code point 241) take?

    A 2B 1C 4

    A. 2

Year 8 · Algorithms: search and sort · Lesson 2 of 5

Key words (1 of 2)

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.

Year 8 · Algorithms: search and sort · Lesson 2 of 5

Key words (2 of 2)

Binary search
Search a sorted list by halving it each step.

The explanation · step 1 of 3

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.

The explanation · step 1 of 3

The maths: Comparisons bubble sort can need

The explanation · step 2 of 3

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].

The explanation · step 3 of 3 · part 1 of 2

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]

The explanation · step 3 of 3 · part 2 of 2

Merge sort (continued)

★Remember

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

Year 8 · Algorithms: search and sort · Lesson 2 of 5

Try it: Bubble sort, one comparison at a time

Year 8 · Algorithms: search and sort · Lesson 2 of 5

Quick quiz · 1 of 3

Which sort splits the list into single items first?

  1. A Insertion sort
  2. B Bubble sort
  3. C Merge sort

C. Merge sort

Split until every piece has 1 item, then merge back in order.

Year 8 · Algorithms: search and sort · Lesson 2 of 5

Quick quiz · 2 of 3

Insertion sort is especially quick when the list is…

  1. A Nearly sorted
  2. B In reverse order
  3. C Very long

A. Nearly sorted

Each item only slides as far as it needs. Nearly sorted means hardly any shifting.

Year 8 · Algorithms: search and sort · Lesson 2 of 5

Quick quiz · 3 of 3

Merge sort is fast on big lists. What's its main cost?

  1. A It needs the list to be sorted first
  2. B It only works on numbers
  3. C It needs extra memory for the merged copies

C. It needs extra memory for the merged copies

Merging builds new lists, so it uses about another n spaces of memory.

Year 8 · Algorithms: search and sort · Lesson 2 of 5

Exit ticket

Answer on paper before you go. Then check.

  1. Binary search only works if the list is…

    A ShortB SortedC Made of numbers

    B. Sorted Throwing away half only makes sense if the list is in order. Sorted words work too.

  2. What is the most checks binary search can need on 1,000 sorted items?

    A 1,000B 500C 10

    C. 10 1,000 halves 9 times to reach 1 (2⁹ = 512), plus one last check: 9 + 1 = 10.