Worksheets › Class 9 › Searching and Sorting › Cheat sheet
Class 9 Searching and Sorting: cheat sheet
CBSE Computational Thinking and AI. Linear search checks every item; binary search halves a sorted list. Bubble sort and selection sort put a list in order pass by pass.
Key ideas
- Linear search checks the items one by one from the left and works on any list.
- Binary search works only on a sorted list: check the middle, then keep the half where the target must be.
- In this chapter positions are numbered 1, 2, 3, …, and the middle is the whole part of (low + high) ÷ 2.
- Bubble sort compares neighbours from left to right and swaps any pair in the wrong order; after each pass the largest unsorted item has reached the end.
- Bubble sort can stop after the first pass that makes no swaps.
- Selection sort finds the smallest item of the unsorted part and swaps it to the front of that part, once per pass.
Remember
| Linear search checks | the position of the item, or all n if it is not there |
| Binary search, worst case for n items | the smallest k with 2ᵏ > n: 100 items → 7, 1,000 → 10 |
| Bubble pass on 5, 1, 4, 2 | 1, 4, 2, 5 (3 swaps) |
| Total bubble swaps | the number of pairs that are out of order |
| Selection sort, n items | n − 1 passes |
Watch out
- Using binary search on a list that is not sorted.
- Thinking one bubble pass sorts the whole list.
- Mixing the two sorts: selection sort swaps the smallest to the front, bubble sort swaps neighbours.
Worked example
Bubble sort swaps neighbouring items that are in the wrong order. How many swaps in all does it make to sort 52, 28, 36, 43, 3, 54?
Working: every swap fixes one out-of-order pair; count those pairs
Answer: 7
Practise Searching and Sorting
Revise with this page, then practise: every Searching and Sorting sheet in the app is new, with an answer key and working.
Coming soon for Android and iPhone.