🎯 Learning Objectives
- Understand how linear search works and evaluate its efficiency
- Understand how bubble sort works (passes and swaps)
- Use abstraction to model real-world problems
- Use subprograms with global/local variables, parameters and return values
- Locate and fix syntax and logic errors
1.1 Linear Search
📘 Key Term: Linear Search
A linear search checks each item in a list one by one, from the beginning, until it finds the target item or reaches the end. It is the simplest search algorithm.
How Linear Search Works
Searching for the number 7 in the list: [3, 8, 1, 7, 5, 2]
It took 4 comparisons to find the item.
Efficiency of Linear Search
| Scenario | Comparisons Needed | Example |
|---|---|---|
| Best case | 1 | Target is the first item |
| Worst case | n (all items) | Target is the last item or not in the list |
| Average case | n ÷ 2 | Target is somewhere in the middle |
💡 Why Does Efficiency Matter?
With a list of 10 items, linear search is fine. But imagine searching through 1 billion items — in the worst case, you'd check all 1 billion! More efficient algorithms (like binary search) can find items in just ~30 comparisons from a billion items.
1.2 Bubble Sort
📘 Key Term: Bubble Sort
Bubble sort repeatedly steps through a list, compares each pair of adjacent items, and swaps them if they're in the wrong order. This is repeated in multiple passes until no swaps are needed, meaning the list is sorted. The largest values "bubble" up to the end.
How Bubble Sort Works
Sort: [5, 3, 8, 1, 2] — Pass 1
Compare 5 and 3 → 5 > 3, so SWAP → [3, 5, 8, 1, 2]
Compare 5 and 8 → 5 < 8, so no swap → [3, 5, 8, 1, 2]
Compare 8 and 1 → 8 > 1, so SWAP → [3, 5, 1, 8, 2]
Compare 8 and 2 → 8 > 2, so SWAP → [3, 5, 1, 2, 8]
After Pass 1: [3, 5, 1, 2, 8] — the largest value (8) has bubbled to the end ✓
⚠️ When Does Bubble Sort Stop?
The algorithm ends when a complete pass is made with no swaps. This means the list is fully sorted. Without this check, the algorithm still works but wastes time doing unnecessary passes.
1.3 Abstraction
📘 Key Term: Abstraction
Abstraction is the process of removing unnecessary details to focus on what's important when solving a problem. A model that represents only the key features of a real-world system is called a computational abstraction.
Examples of abstraction in the real world:
🗺️ Transport Maps
The London Underground map removes real geographical distances and focuses on station order and connections.
🍳 Recipes
A recipe is an abstraction of cooking. It lists ingredients, quantities and steps — hiding the complex chemistry.
🎮 Simulations
A speed camera simulator models only the relevant variables (speed, distance, time) without modelling the entire road.
🌡️ Greenhouse Controller
Models temperature, humidity and watering — ignoring irrelevant details like the colour of the greenhouse.
1.4 Global and Local Variables
📘 Key Terms
Local variable — declared INSIDE a subprogram. It only exists while that subprogram is running and cannot be accessed from outside it.
Global variable — declared OUTSIDE all subprograms. It can be accessed from anywhere in the program.
1.5 Parameters and Return Values
📘 Key Terms
Parameter — a variable listed in a subprogram's definition that receives a value when the subprogram is called.
Argument — the actual value passed to the parameter when calling the subprogram.
Return value — the result sent back to the calling
code using the return keyword.
📝 Activity 1.1 — Card Sort Simulation
- Take 10 numbered cards (or write numbers on paper strips)
- Shuffle them randomly
- Perform a bubble sort by hand — record how many passes and swaps you need
- Now use a linear search to find a specific number — count the comparisons
- Write Python programs implementing both algorithms
- Test with lists of 10, 100 and 1000 items — what do you notice about speed?
📋 Chapter 1 Summary
- Linear search checks each item one by one — simple but slow for large datasets
- Bubble sort compares adjacent pairs and swaps them — repeats until no swaps needed
- Abstraction removes unnecessary detail to model real-world problems
- Local variables exist only inside their subprogram; global variables are accessible everywhere
- Parameters receive values; return values send results back to the calling code
✅ Check Your Understanding
1. How many comparisons does a linear search need in the worst case for a list of 50 items?
2. What is a "pass" in bubble sort? When does the algorithm stop?
3. Give a real-world example of abstraction and explain what details are removed.
4. What is the difference between a local and a global variable?
5. What is the difference between a parameter and an argument?