Describe and implement the standard searching and sorting algorithms (linear and binary search, bubble, insertion and quicksort), explain recursion, and compare algorithm efficiency.

What this dot point is asking

The SQA wants you to know the standard searching and sorting algorithms, to be able to trace and implement them, to explain recursion, and to compare how efficient algorithms are as the data grows. Efficiency, not just correctness, is examined at Advanced Higher.

Searching algorithms

A linear (sequential) search examines each item from the start until it finds the target or reaches the end. It works on any list, sorted or not, but is slow on large lists because it may check every item.

A binary search is much faster but needs a sorted list. It compares the target with the middle item; if they match it stops, otherwise it discards the half that cannot contain the target and repeats on the remaining half. Each step halves the search space.

Sorting algorithms

A bubble sort makes repeated passes, comparing each adjacent pair and swapping them if they are out of order; the largest unsorted value "bubbles" to the end each pass. It is simple but slow, doing on the order of n-squared comparisons.

An insertion sort keeps a growing sorted section at the front and takes each next item, shifting larger items right until it can drop the new item into its correct place. It is efficient on nearly-sorted data but still on the order of n-squared in the worst case.

A quicksort chooses a pivot, partitions the remaining items into those smaller and those larger than the pivot, then sorts each partition the same way (recursively). It averages about n log n, much faster than bubble or insertion sort on large lists.

Recursion

Recursion is when a routine calls itself to solve a smaller instance of the same problem. Every recursive routine needs two parts: a base case that returns directly without recursing (so the process stops), and a recursive case that reduces the problem and calls itself. Recursion expresses naturally divide-and-conquer algorithms such as quicksort and structures such as traversing a tree.

Comparing efficiency

Efficiency describes how an algorithm's work grows as the input size n grows, independent of the particular machine. A linear search grows in proportion to n; a binary search grows in proportion to log n; bubble and insertion sort grow in proportion to n-squared; quicksort averages n log n. The faster-growing the cost, the worse the algorithm scales, so for large n the difference between n-squared and n log n is enormous. You compare algorithms by this growth, not by timing a single run on one machine.

Try this

Q1. State the precondition a binary search requires. [1 mark]

• Cue. The list must be sorted.

Q2. State roughly how the number of comparisons grows with list size n for a linear search. [1 mark]

• Cue. In proportion to n (up to n comparisons), because it may check every item.