S6 ICT: Sorting and Searching Algorithms
- 2026-11-20
S6 ICT: Sorting and Searching Algorithms
The first paper starts from the ground: what sorting is, how many steps a linear search takes, and why binary search insists on sorted data.
Basics: scanning one by one versus halving Linear search takes up to 8 comparisons on 8 items and about 4 on average, while binary search needs 3 because 2^3 = 8. Bubble sort needs at most 7 passes and 28 comparisons on 8 items, and selection sort swaps at most 4 times on 5. Every figure is written as a formula and checked in Python.
01 Paper details (check answers afterwards)
| Item | Detail |
|---|---|
| Questions | 10 |
| Suggested time | 25 |
| Difficulty mix | Foundation 3 · Intermediate 3 · Challenge 3 · Error redo 1 |
| Chapter | Chapter: S6 ICT: Sorting and Searching Algorithms |
| Level | Basics (10 items) |
02 Questions (10 items)
- FoundationWhat is sorting, and why sort before searching?
- FoundationSearching 8 unsorted items linearly for a value that is absent, what is the worst-case number of comparisons?
- FoundationFor the same 8 items, what is the average number of comparisons a successful linear search makes?
- IntermediateWhat is the essential precondition for binary search?
- IntermediateIn 8 sorted items, what is the maximum number of comparisons binary search makes?
- IntermediateHow many passes does bubble sort need at most for 8 items?
- ChallengeHow many comparisons does bubble sort make in the worst case for 8 items?
- ChallengeHow many swaps does selection sort perform at most on 5 items?
- ChallengeBubble sorting [3, 1, 2] ascending, what is the array after the first pass?
- Error redoError: someone claims binary search is always faster than linear search. What is wrong?
03 Answers and one-line notes
| # | Answer | One-line note |
|---|---|---|
| 1 | Sorting rearranges data into order by some criterion; once ordered, binary search cuts the range in half each step instead of comparing one by one. | Sorting has a cost, but it pays off when the same data is searched many times. |
| 2 | At most 8, comparing all 8 items one by one. | Linear search has no rule for skipping items, so the worst case visits every one of the 8. |
| 3 | About 4, since the successful position averages the middle of 1 to 8. | The average of positions 1 to 8 is 8/2 = 4. |
| 4 | The data must already be sorted by the same criterion, with random access. | Discarding half after comparing the midpoint relies on everything left being smaller and right being larger; unsorted data gives no such guarantee. |
| 5 | At most 3, because 2^3 = 8. | Each comparison halves the range, so 8 items shrink to one in 3 steps. |
| 6 | At most 7, since each pass fixes one item into its final place. | One item settles per pass, so 8 items need 8 – 1 = 7 passes. |
| 7 | 28, that is 7 passes of decreasing length. | The total is 8(8-1)/2 = 28, so bubble sort is O(n^2) in the worst case. |
| 8 | At most 4, that is 5 – 1. | Each pass swaps exactly one minimum into place, over 4 passes. |
| 9 | [1, 2, 3]: 3 swaps with 1 giving [1, 3, 2], then 3 swaps with 2 giving [1, 2, 3]. | This list finishes in a single pass because the maximum 3 bubbles straight to the end. |
| 10 | Binary search needs sorted data, so unsorted input adds sorting cost, and for tiny inputs a linear scan is faster and simpler. | Compare total cost including sorting and the problem size, not a single search alone. |
04 What to do after marking
- After marking, redo only the wrong items and write down which step went wrong (formula, unit, or misread number).
- Repeat the same item two days later; move to the next paper only when both attempts are correct.
- Parents only need the answer and note columns; there is no need to explain every item.
Want to separate bubble, selection, insertion and merge sort, then replace a linear scan with binary search? Book a TutorZone tutor and count every comparison in twenty-five minutes.Tutor Registration →
Questions and answers are written originally by the TutorZone team and are not taken from any school, publisher or examination authority paper. Every value is checked by computer.



