An algorithm is a set of steps that solves a problem. This topic covers how algorithms are written down, how they are checked, and the standard searching and sorting algorithms.
An algorithm is a sequence of steps that can be followed to complete a task. It must be unambiguous and must finish.
A computer program is an implementation of an algorithm. The algorithm is the plan; the program is one way of expressing it in a particular language.
Decomposition means breaking a problem into smaller sub-problems, each of which accomplishes an identifiable task. A sub-problem can itself be broken down further.
Smaller problems are easier to solve, easier to test, and can be shared between people.
Abstraction is removing detail that does not affect the solution. A map of a railway removes the true distances and curves because a passenger needs only the order of the stops.
An algorithm can be written as pseudo-code, as program code, or as a flowchart.
In a flowchart the shapes have fixed meanings:
In pseudo-code, indentation shows which statements sit inside a loop or a decision.
Every algorithm can be described as taking an input, carrying out processing, and producing an output. Identifying the three separately is the first step in designing a solution.
A structure diagram shows how a problem decomposes. The whole problem sits at the top, and each level below breaks the level above into smaller parts. It shows the structure of a solution, not the order in which steps run.
A trace table records the value of each variable after every step. It is used to work out what an algorithm does, or to find where it goes wrong.
Working through an algorithm by hand in this way is called a dry run.
More than one algorithm can solve the same problem. Comparing them usually means comparing how much work each does: the number of comparisons made, or the number of times a loop repeats.
At GCSE the comparison is described in words rather than calculated formally.
A linear search checks each item in turn from the start until it finds the target or reaches the end.
It works on any list, sorted or not. For a list of n items it may need up to n comparisons.
A binary search checks the middle item. If that is not the target, it discards the half that cannot contain it and repeats on what remains.
The list must already be sorted. Each comparison halves the remaining search area.
Binary search usually needs far fewer comparisons on a large list, but the data has to be sorted first.
Linear search needs no sorting, so it suits short lists and lists that change often.
A bubble sort compares each adjacent pair and swaps them if they are in the wrong order. One pass moves the largest remaining item to its final place.
A list of n items needs at most n − 1 passes. It is simple to write but slow on long lists.
A merge sort splits the list repeatedly until every part holds one item, then merges the parts back together in order.
It is generally much faster than bubble sort on a long list, but it needs extra memory while merging.
An insertion sort builds a sorted section at the front of the list. Each new item is taken in turn and placed at the right point within that section.
Bubble and insertion sorts are simple to implement and use little extra memory, which suits short lists.
Merge sort handles long lists far faster, at the cost of extra storage.
A subroutine is a named block of code that performs one task and can be called from anywhere in a program. Using subroutines avoids repeating the same steps and keeps each part small enough to test on its own.
Validation checks that data entered follows the rules the program expects. Common checks are a range check, a length check, a presence check and a format check.
Validation cannot tell whether data is true, only whether it is possible.
Three kinds of test data are used:
