Computer Science › Section F · Algorithms › Topic F.4

Iterative structures: sequential search and insertion sort

Most useful algorithms repeat something: check the next entry, move the next card, pour the next drop. This topic shows how loops are controlled so that they always finish, then uses them to build two classic algorithms, sequential search and insertion sort.

Why loops

A loop repeats a group of instructions, called its body, under the direction of a control. Writing a step out three times works if you know it must happen three times, but often you do not. "While the bath is not full, pour in another jug of water" cannot be replaced by a fixed list of steps, because nobody knows how many jugs it will take. This topic uses the pseudocode from "Representing algorithms with pseudocode", where L[i] is the entry at position i and positions run from 1 to length(L).

Loop control: initialise, test, modify

Controlling a loop takes three activities. Initialise sets up a starting state. Test compares the state with the termination condition, the condition under which the loop should stop. Modify changes the state so that it moves towards that condition. A while loop states the condition for continuing, so its termination condition is the opposite: while (Count < 20) stops once Count >= 20. The control, not the body, is where loops usually go wrong. In X = 0 followed by while (X != 10): X = X + 3, X takes the values 0, 3, 6, 9, 12 and so on and jumps over 10, so the loop never ends. The modify step must really lead to the termination condition.

Pretest and posttest loops

A while loop is a pretest loop: it checks its condition before every pass, so if the condition is false at the start the body never runs. A repeat ... until loop is a posttest loop: it runs the body first and checks afterwards, so the body always runs at least once. Asking for a PIN suits a posttest loop, repeat: ask for the PIN, until (the PIN is correct), because you must ask at least once. Removing items from a bag suits a pretest loop, while (the bag is not empty): remove an item, because the bag might be empty to begin with.

For-each loops

Many loops simply visit every entry of a list in order, and for X in List: does exactly that, with X standing for each entry in turn. It hides the three control activities: start at the first entry, move to the next, stop when the entries run out. Adding up a list is a typical use: Sum = 0, then for X in List: Sum = Sum + X. A for-each loop is a pretest loop, so for an empty list the body never runs and Sum stays 0.

The sequential search algorithm

To decide whether a target value appears in a list, check the entries one by one from the front. This is the sequential search, also called linear search.

\begin{array}{l} \texttt{def Search(L, Item):} \\ \quad \texttt{Position = 1} \\ \quad \texttt{while (Position <= length(L)} \\ \qquad\quad \texttt{and L[Position] != Item):} \\ \qquad \texttt{Position = Position + 1} \\ \quad \texttt{if (Position <= length(L)):} \\ \qquad \texttt{return Position} \\ \quad \texttt{return 0} \end{array}

It returns the position of Item, the target, or 0 if it is absent. Our and checks its left side first and skips the right side when the left is false, so L[Position] is never read past the end. The loop stops when Position > length(L) or L[Position] == Item: the opposite of an and is an or of the opposites.

Worked example: tracing a sequential search

Search L = [14, 8, 29, 3, 17] for 29. 1. Position 1: 14 is not 29, so move on. 2. Position 2: 8 is not 29. 3. Position 3: 29 matches, so the loop stops and the function returns 3, after 3 comparisons. Now search for 5. 4. All five entries are compared and none matches. 5. Position becomes 6, which exceeds length(L), so the function returns 0 after 5 comparisons. On a list of n entries, a failed search always makes n comparisons, and a successful one makes about n/2 on average. If the list is sorted, the search can stop early at the first entry that is too big: searching [3, 8, 14, 17, 29] for 10 stops at 14 after 3 comparisons.

The idea of insertion sort

Think of sorting playing cards as you pick them up: you slide each new card left past every larger card and drop it into the gap. Insertion sort does the same within the list itself, using no second list. The front part of the list is the sorted part, starting with just the first entry. Each pass lifts the next entry out as the Key, shifts the larger sorted entries one place to the right, and puts the Key into the hole that opens up. After the pass for position N, the first N entries are in order. Selection sort, a common alternative, instead finds the smallest unsorted entry and swaps it to the front of the unsorted part. Both take roughly \(n^2\) steps on long lists, but only insertion sort speeds up on a nearly sorted list.

Insertion sort in pseudocode

\begin{array}{l} \texttt{def InsertionSort(L):} \\ \quad \texttt{N = 2} \\ \quad \texttt{while (N <= length(L)):} \\ \qquad \texttt{Key = L[N]} \\ \qquad \texttt{Hole = N} \\ \qquad \texttt{while (Hole > 1} \\ \qquad\qquad \texttt{and L[Hole - 1] > Key):} \\ \qquad\quad \texttt{L[Hole] = L[Hole - 1]} \\ \qquad\quad \texttt{Hole = Hole - 1} \\ \qquad \texttt{L[Hole] = Key} \\ \qquad \texttt{N = N + 1} \end{array}

This is a loop within a loop. The outer loop initialises N = 2, modifies it with N = N + 1, and stops when N exceeds length(L). The inner loop is initialised by lifting out the Key, modified as the hole moves left, and stops when the hole reaches the front or the entry before it is not greater than the Key.

Worked example: tracing insertion sort

Sort [7, 3, 9, 1, 5], counting each test of L[Hole - 1] > Key as one comparison. 1. N = 2, Key = 3: 7 > 3, so 7 shifts right; the hole reaches the front. List [3, 7, 9, 1, 5], 1 comparison. 2. N = 3, Key = 9: 7 > 9 is false, so 9 stays. 1 comparison. 3. N = 4, Key = 1: 9, 7 and 3 are all greater, so all shift. List [1, 3, 7, 9, 5], 3 comparisons. 4. N = 5, Key = 5: 9 and 7 shift, then 3 > 5 is false. List [1, 3, 5, 7, 9], 3 comparisons. 5. Total: 8 comparisons. An already sorted list of n entries needs only n - 1 comparisons, one per pass.

Common mistakes to avoid

First, a modify step that skips the termination value, as in counting by 3 towards 10 with !=; testing with < is safer. Second, forgetting the modify step, so the state never changes. Third, using a posttest loop when the body may be unsafe to run even once. Fourth, writing >= instead of > in the insertion sort's inner loop: equal entries would then be swapped needlessly and lose their original order, so the sort would no longer be stable. Fifth, reading L[Position] before checking Position <= length(L).

Key takeaways

A loop repeats a body under a control made of initialise, test and modify, and the modify step must lead to the termination condition, the opposite of a while loop's condition. while is a pretest loop that may run zero times; repeat ... until is a posttest loop that runs at least once; for X in List visits every entry. Sequential search checks entries in order and makes up to n comparisons. Insertion sort grows a sorted front part by lifting each Key and shifting larger entries right; it is in place and stable, and needs n - 1 comparisons on a sorted list.

Flashcards

Flashcard

Loop body

The instructions a loop repeats

Run under the direction of the loop's control.

Test your understanding

Question 1 of 5

A loop begins while (Count < 20 and not Found). What is its termination condition?

Question 2 of 5

Number starts at 5. Then: repeat: Number = Number + 1, until (Number > 3). What is Number afterwards?

Question 3 of 5

Sequential search looks for 19 in the list 12, 5, 30, 7, 19, 2. How many comparisons with the target does it make?

Question 4 of 5

Insertion sort, as in the worked example, sorts 6, 2, 8, 4. How many comparisons does it make in total?

Question 5 of 5

Why does insertion sort's inner loop test L[Hole - 1] > Key rather than >= Key?

← Previous topicNext topic →