Search & Sort

Four algorithms to know cold 🔎

Two jobs come up again and again in computing: **searching** for an item in a list, and **sorting** a list into order. The exam expects four named algorithms for these jobs. For searching: **linear search** and **binary search**. For sorting: **bubble sort** and **merge sort**. This module shows how each one works, and - just as importantly - how to judge which is **faster** by counting the work it does.

The four in one place 🗂️

One line each - the detail comes next.

Two ways to search ⚖️

Both find an item, but they work very differently - and one has a strict condition.

The golden rule 📑

What MUST be true about a list before you can use a binary search on it?

• The list must already be sorted into order
• The list must be short
• The list must contain only numbers
• Every item must be unique

Order the binary search 🪜

An interactive activity.

Trace the binary search 📊

An interactive activity.

Which half survives? ✂️

In a binary search on a list sorted smallest-to-largest, the middle value turns out to be SMALLER than the target. Which half do you keep?

• The upper half (larger values), above the middle
• The lower half (smaller values), below the middle
• Keep both halves and check them all
• Start again from the beginning

Two ways to sort 🫧

Now for sorting. Both put a list in order, but they scale very differently.

What one pass of bubble sort does 🔁

During a single pass of a bubble sort, what does the algorithm actually do?

• Compares each adjacent pair and swaps them if they are in the wrong order
• Checks the middle item and discards half the list
• Splits the list into two halves to sort separately
• Finds the single smallest item and stops

Match each algorithm to its key idea 🔗

Count the comparisons 🔢

An interactive activity.

True of binary search? ✅

Select the TWO statements that are true of a binary search.

• It needs the list to be sorted first
• It roughly halves the items left to check at each step
• It works on a list in any order
• It checks every item one by one

How we measure "faster" 📈

A grade-9 answer never just says "it is faster" - it counts the work:\n\n- **Comparisons**: how many items are checked (linear search checks up to n; binary search only about log2(n)). - **Passes / swaps**: how many times a sort loops through the list (bubble sort needs many passes on a long list). - **Memory use**: merge sort is fast but needs extra space to hold the split lists; bubble sort needs almost none. Judge an algorithm on a **concrete count**, not a feeling.

Pick the right algorithm 🧭

An interactive activity.

Your turn: which search, and why? ✍️

An interactive activity.

The grade-9 habit 🌟

Match the algorithm to the job. To **search**: linear search on any list but slow; binary search only on a **sorted** list, but fast because it halves the list each step. To **sort**: bubble sort is simple but slow; merge sort is a fast **divide-and-conquer** method that needs more memory. And when you compare them, **count the work** - comparisons, passes, memory - never just say "it is faster". A concrete number is what earns the mark.