Standard methods of solution

Computer Science · Algorithm design and problem-solving. The idea in plain words, the rules to remember, the mistake to avoid and a worked example, written and checked by Mega Lecture.

Test this topic free All Computer Science topics

The idea

Some small algorithms are used so often that you must know them by heart.

A linear search looks for a value by checking each item of a list in turn, from the first item, until the value is found or the end of the list is reached. A bubble sort puts a list in order. It compares each pair of neighbouring items and swaps them if they are in the wrong order. One journey through the list is a pass, and passes are repeated until a whole pass makes no swaps.

Totalling adds each value to a running total. Counting adds 1 each time something happens. The same loop idea is used to find the maximum, minimum and average.

Rules to remember

Linear search: the number of comparisons equals the position of the item. If the item is not in a list of n items, all n are compared.
Bubble sort: the first pass through n items makes n − 1 comparisons and, for ascending order, moves the largest value to the end.
A flag such as Swapped stops the bubble sort early when a pass makes no swaps.
Totalling: Total ← Total + Value. Counting: Count ← Count + 1. Both must be set to 0 before the loop.
Maximum: start Highest at the first item, then IF Value[i] > Highest THEN Highest ← Value[i].
Minimum: start Lowest at the first item, then replace it whenever a smaller value is found.
Average = Total ÷ Count, calculated once, after the loop has finished.

Common mistake

Starting Highest at 0 gives a wrong answer when all the values are negative. Start Highest (or Lowest) at the first item in the list.

Worked example

An array holds 7, 2, 9, 4. A bubble sort puts it into ascending order. What does the array hold after the first pass, and how many comparisons were made?

Compare 7 and 2: wrong order, so swap. The array is now 2, 7, 9, 4.
Compare 7 and 9: correct order, so no swap. The array is still 2, 7, 9, 4.
Compare 9 and 4: wrong order, so swap. The array is now 2, 7, 4, 9.
There are 4 items, so the pass made 4 − 1 = 3 comparisons.

Answer: After the first pass the array holds 2, 7, 4, 9, and 3 comparisons were made.

Ask about this

Type what you are stuck on. The helper finds the explanation, worked examples and the notes to read, free and instant.

Keep going

← Program development life cycle and decomposition Validation, verification and test data →Take a Computer Science test