Year 8 · Summer 1

Algorithms: search and sort · Lesson 4 of 5

Comparing efficiency by counting comparisons

TheoryTopic 12 Searching and sorting

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

You will learn to

  • Count the comparisons a search or a sort makes on a short list.
  • Compare how the number of comparisons grows when the list doubles in length.
  • Explain that n² grows much faster than n log n as the list gets longer.
  • Choose an algorithm for a situation: sorted or not, big or small.

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

Success criteria

You have got it when you can say:

  • I can fill in a table of comparisons for lists of 8, 16 and 32 items.
  • I can say that doubling a list adds only one check to a binary search.
  • I can choose a search or a sort for a scenario and give a reason.

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

Retrieval starter

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

  1. Last lesson

    Insertion sort is especially quick when the list is…

    A Nearly sortedB In reverse orderC Very long

    A. Nearly sorted

  2. Last unit

    What does print("3" + "4") show?

    A 7B 34C An error

    B. 34

  3. Earlier this year

    11111111 (255) + 1 in 8 bits causes…

    A Nothing specialB OverflowC 256

    B. Overflow

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

Key words (1 of 2)

Linear search
Check every item in turn.
Binary search
Search a sorted list by halving it each step.
Bubble sort
Swap neighbours until a whole pass makes no swaps.
Insertion sort
Slide each item into its place in the sorted part.

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

Key words (2 of 2)

Merge sort
Split into single items, then merge back in order.

The explanation · step 1 of 1

Comparing them

AlgorithmNeeds sorted?Speed on big listsEasy to code?
Linear searchNoSlowVery
Binary searchYesVery fastFairly
Bubble sort—Very slowVery
Insertion sort—Slow (fast if nearly sorted)Fairly
Merge sort—Fast (uses extra memory)Harder
★Remember

There's rarely one best algorithm, only the best one for this data.

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

Quick quiz · 1 of 3

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

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

A. 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 4 of 5

Quick quiz · 2 of 3

Binary search only works if the list is…

  1. A Sorted
  2. B Made of numbers
  3. C Short

A. Sorted

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

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

Quick quiz · 3 of 3

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

  1. A 500
  2. B 1,000
  3. C 10

C. 10

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

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

Exit ticket

Answer on paper before you go. Then check.

  1. A linear search on 50 unsorted items, looking for something that is not there, makes…

    A 1 checkB 25 checksC 50 checks

    C. 50 checks It can only say 'not found' after checking every item: the worst case, n = 50.

  2. Bubble sort compares…

    A The first and last itemsB NeighboursC Random pairs

    B. Neighbours Items next to each other, swapping them if they're in the wrong order.