Retrieval Starter
Can you reorder the Linear Search logic?
1. return "Not Found"
2. if list[i] == target:
3. for i from 0 to len(list):
4. return i
The "Red Zone" Focus
We are targeting Midpoint Logic and Efficiency Tracing. These are high-mark areas where students often lose "off-by-one" marks.
1. Searching Algorithms
Linear Search
Checks every element in the list one by one until the target is found or the end is reached.
- Works on unsorted lists.
- Efficiency: O(n) - Time taken increases directly with list size.
Binary Search
Uses a "Divide and Conquer" strategy by repeatedly halving the search area.
Mandatory Requirement:
The list MUST be sorted before a binary search can begin.
Midpoint Logic Drill
Formula: midpoint = (low + high) // 2 (Integer Division)
List Length: 7
Indices: 0 to 6
Midpoint: 3
List Length: 8
Indices: 0 to 7
Midpoint: 3
List Length: 9
Indices: 0 to 8
Midpoint: 4
EXAMINER TIP: Ensure you update Low to (Mid + 1) or High to (Mid - 1) to avoid infinite loops.
2. Sorting Algorithms
Bubble Sort
Compares adjacent pairs and swaps them if they are in the wrong order. Smallest values "bubble" to the start (or largest to the end).
Pass 1 Example:
[5, 1, 4, 2]
- 1. Compare 5 & 1 ā Swap: [1, 5, 4, 2]
- 2. Compare 5 & 4 ā Swap: [1, 4, 5, 2]
- 3. Compare 5 & 2 ā Swap: [1, 4, 2, 5]
End of Pass 1: [1, 4, 2, 5]
Merge Sort
A "Divide and Conquer" algorithm. It recursively splits the list into individual elements and then merges them back in order.
3. Efficiency & Comparison
| Algorithm | Best Case | Worst Case | When to use? |
|---|---|---|---|
| Linear Search | Item at start | Item not in list (O(n)) | Small unsorted datasets |
| Binary Search | Item in middle | Many steps (O(log n)) | Large sorted datasets |
| Bubble Sort | Already sorted | Reverse sorted (O(nĀ²)) | Very small lists |
| Merge Sort | O(n log n) | O(n log n) | Large datasets (Fastest) |
Exam Practice | 25 Minutes
Algorithm Questions - Turn theory into marks!
State two differences between bubble sort and merge sort.
- Bubble sort compares adjacent items whereas merge sort is a divide-and-conquer algorithm that splits the list.
- Bubble sort has a worst-case efficiency of O(nĀ²) however merge sort is more efficient with O(n log n).
The list [6, 2, 8, 3, 5] needs to be sorted using bubble sort.
Show the state after each pass and explain early termination.
Passes:
- [2, 6, 3, 5, 8]
- [2, 3, 5, 6, 8]
- [2, 3, 5, 6, 8] (Final check)
Explanation: The algorithm stops early because a full pass (Pass 3) occurred with no swaps, indicating the list is sorted.
A program crashes when the user enters 0. Identify the type of error and explain why it occurs. Describe prevention.
- Type: Runtime Error (Division by Zero).
- Cause: Attempting to divide a number by zero, which is mathematically undefined and crashes the process.
- Prevention: Use input validation (e.g.,
if divisor != 0:) to check the value before the division.
Explain why merge sort is more efficient than bubble sort for 10,000 items. Use Big O notation.
Merge sort has a time complexity of O(n log n) whereas bubble sort is O(nĀ²).
Bubble: 10,000Ā² = 100,000,000 ops
Merge: 10,000 Ć 13.3 ā 133,000 ops
This means merge sort performs significantly fewer operations as the dataset grows large, resulting in much faster execution.