Algorithms with Branching: Sorting and Searching

Algorithms can branch with if–otherwise. This chapter traces branches, does a pass of bubble sort, and searches by checking or by halving.

Key ideas

An if–otherwise step checks its condition with the CURRENT value each round, so the branch can change from round to round.
One pass of bubble sort compares neighbours from the left and swaps them if the left one is bigger.
After one pass, the largest number has moved to the end of the list.
Linear search checks the items one by one from the left; it works on any list.
Guessing the middle of what is left halves the choices each time, so very few guesses are needed.
To debug a trace, find the first step whose result does not follow from the one before.

Remember

One bubble pass on 5, 2, 8, 1	2, 5, 1, 8 (2 swaps)
Linear search	checks = position of the item
Most halving guesses for 1 to N	smallest k with 2ᵏ − 1 ≥ N
Examples	1 to 100: 7 guesses; 1 to 1000: 10
Branch trace	x = 15, if x > 22 take 7 else add 7: 15 → 22 → 29 → 22

Watch out

Sorting the whole list when only one pass is asked.
Comparing a number with the one two places away instead of its neighbour.
Using the starting value in every round of a branch trace.

Worked example

(a) x = 15
Repeat 5 times:
If x > 22, x = x − 7
Otherwise, x = x + 7
What is x at the end?
(b) Start with the row K, J, G, R, C. (1) Move the first letter to the end. (2) Reverse the whole row. (3) Swap the letters in places 1 and 4. (4) Swap the letters in places 1 and 3. What is the row now?

Working: (a) 15 → 22 → 29 → 22 → 29 → 22; (b) carry out each instruction in order: R C G K J

Answer: (a) 22; (b) R, C, G, K, J