Worksheets › Class 7 › Algorithms with Branching: Sorting and Searching › Cheat sheet
Class 7 Algorithms with Branching: Sorting and Searching: cheat sheet
CBSE Computational Thinking and AI. 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
Practise Algorithms with Branching: Sorting and Searching
Revise with this page, then practise: every Algorithms with Branching: Sorting and Searching sheet in the app is new, with an answer key and working.
Coming soon for Android and iPhone.