Tracing, sorting and searching algorithms

What you’ll learn

• Trace a precise sequence of algorithm steps.
• Perform bubble sort and quick sort consistently.
• Apply binary search to a sorted list.

Understand the idea

An algorithm is a finite set of unambiguous steps. Trace it by recording the changing list, variable values and decision outcomes, rather than jumping straight to the expected answer. A flowchart decision has alternative branches, and a loop condition must be checked at the stated point.

In an ascending bubble sort scanning left to right, compare adjacent entries and swap those in the wrong order. One complete pass places the largest remaining value at the right end. In quick sort, choose the middle entry as pivot, partition the other entries into smaller and larger groups, then repeat within each group. For an even-length list, use the right-hand middle entry under the convention used here.

Binary search requires a sorted list. Compare the target with the middle entry, discard the half that cannot contain it, and repeat on the remaining ordered portion. Record the tested entries to show the method. A fully sorted result does not by itself demonstrate that the requested algorithm was followed.

Key formulae

$$m=\left\lfloor\frac N2\right\rfloor+1\quad\text{(1-based middle position)}$$

$$a_i>a_{i+1}\ \Longrightarrow\ (a_i,a_{i+1})\mapsto(a_{i+1},a_i)$$

Worked example

Perform an ascending bubble sort on (7, 2, 9, 4, 1), scanning left to right. Show the list after each swapping pass.

1. Pass 1 compares adjacent entries and ends at (2, 7, 4, 1, 9). The 9 is fixed at the right.
2. Pass 2 ends at (2, 4, 1, 7, 9).
3. Pass 3 ends at (2, 1, 4, 7, 9).
4. Pass 4 ends at (1, 2, 4, 7, 9), completing the ordered list. A further no-swap check can confirm termination if that version of the algorithm requires it.

Answer: Sorted list: (1, 2, 4, 7, 9).