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

Put the steps of a binary search (on a sorted list) into the correct order.

• Look at the item in the middle of the list
• Compare it with the target you are searching for
• If it matches, stop - you have found the item
• If not, discard the half that cannot contain the target
• Repeat on the half that remains until found or none left

Trace the binary search

Searching the sorted list [1, 3, 5, 7, 9, 11, 13] (positions 1 to 7) for the target 13. Each pass, work out mid = (low + high) DIV 2. The value at mid is too small, so keep the UPPER half (low becomes mid + 1). Fill in each mid.

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

A list has 8 items in no particular order and you use a LINEAR search. In the worst case (the item is last, or not there at all), how many items does it check?

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

Three real situations. Choose the best algorithm for each.

• You have an UNSORTED list of names and need to find one, just this once. Which is the sensible choice?
• You have a large, ALREADY SORTED list that you search many times a day. Which search is most efficient?
• You must sort a very large list and you care about speed. Which sort scales best?

Your turn: which search, and why?

A shop keeps a long, sorted list of product codes. Explain why a binary search finds a code faster than a linear search, and state the one condition binary search needs. Back it up by talking about the number of comparisons.

• State the condition: binary search needs the list to be sorted
• Explain that binary search discards half the items at each step
• Contrast the comparison counts: linear checks up to every item (n); binary only about log2(n)
• Conclude which is faster on a long sorted list and why

Match the algorithm to the job

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.