Computer Science - ICT Grade 7: Algorithms Sorting and Searching

Grade 7 Computer Science – Algorithms: Sorting and Searching

1. The Driving Question

"If you have a giant stack of messy homework papers—some math, some science, some history—and your teacher says, ‘Find the one with the lowest grade fast,’ how do you do it without reading every single page? And if you want to line them up from worst to best, how do you decide where each one goes without making a bigger mess?"

2. The Core Idea – Built, Not Listed

Imagine your little brother’s toy chest is a disaster: action figures, Legos, and stuffed animals all jumbled together. You need to find his favorite dinosaur right now before he melts down. If the toys were sorted by type (all dinosaurs in one bin, all cars in another), you could just grab the dinosaur bin and dig through 10 toys instead of 100. Sorting is like organizing the mess so searching becomes faster.

But how do you sort them? One way is to pick up two toys at random and swap them if they’re out of order—like putting the car after the dinosaur if you’re sorting by size. Keep doing this until everything’s in the right place. This is called Bubble Sort, and it’s slow but simple. A faster way is to split the pile in half, sort each half, then merge them back together—like sorting two smaller toy chests and then combining them. This is Merge Sort, and it’s what computers use when they have to sort millions of things.

Now, searching: if the toys are sorted, you don’t have to check every single one. You can start in the middle—if the middle toy is a dinosaur, you know the one you want is before it (if it’s smaller) or after it (if it’s bigger). This is Binary Search, and it’s way faster than checking every toy one by one.

Key Vocabulary: - Algorithm: A step-by-step set of instructions to solve a problem. Example: The recipe for making a peanut butter sandwich is an algorithm—if you skip a step (like opening the jar), the sandwich fails. - Bubble Sort: A sorting algorithm that repeatedly swaps adjacent items if they’re in the wrong order. Example: Sorting a deck of cards by repeatedly flipping two cards at a time until the whole deck is in order. Note: In real-world programming, Bubble Sort is too slow for large datasets, but it’s great for learning how sorting works. - Binary Search: A search algorithm that finds an item in a sorted list by repeatedly dividing the search range in half. Example: Guessing a number between 1 and 100 by always asking, “Is it higher or lower than 50?” instead of guessing 1, 2, 3, etc. - Efficiency: How fast an algorithm runs, usually measured in how many steps it takes. Example: Binary Search is efficient because it takes at most 7 guesses to find a number between 1 and 100, while checking every number could take 100 guesses.

3. Assessment Translation

How This Appears on State Tests (Grade 7): - Multiple Choice: Questions will ask you to identify which algorithm is being used (e.g., “Which algorithm repeatedly compares adjacent items?”) or predict the next step in a sorting process. - Distractor Patterns: Wrong answers might show a step from a different algorithm (e.g., Merge Sort instead of Bubble Sort) or a step that violates the rules (e.g., skipping a comparison). - Short Answer: You might be given a list of numbers and asked to show the steps of Bubble Sort or Binary Search. Proficient responses include: - Correctly swapping numbers in Bubble Sort (e.g., “Swap 5 and 3 because 5 > 3”). - Showing the “divide in half” logic of Binary Search (e.g., “The list is [2, 4, 6, 8]. I check 6 first. 6 > 4, so I search the left half”). - Evidence-Based Writing: A prompt might ask, “Why is Binary Search faster than Linear Search? Use an example to explain.” Proficient responses: - Compare the number of steps (e.g., “Binary Search takes 3 steps to find 7 in [1, 3, 5, 7, 9, 11], while Linear Search takes 4”). - Explain the sorted requirement (e.g., “Binary Search only works if the list is already sorted”).

Model Proficient Response (Short Answer): Prompt: Show the first pass of Bubble Sort on the list [4, 2, 5, 1]. Response:
1. Compare 4 and 2. 4 > 2, so swap them-[2, 4, 5, 1]
2. Compare 4 and 5. 4 < 5, so no swap-[2, 4, 5, 1]
3. Compare 5 and 1. 5 > 1, so swap them-[2, 4, 1, 5] After one pass, the list is [2, 4, 1, 5].

4. Mistake Taxonomy

Mistake 1: Skipping Comparisons in Bubble Sort - Prompt: Show the first pass of Bubble Sort on [3, 1, 4, 2]. - Common Wrong Response: 1. Swap 3 and 1-[1, 3, 4, 2] 2. Swap 4 and 2-[1, 3, 2, 4] Stops here. - Why It Loses Credit: The student didn’t compare every adjacent pair in the first pass. They missed comparing 3 and 4 (which are already in order). - Correct Approach: 1. Compare 3 and 1-swap-[1, 3, 4, 2] 2. Compare 3 and 4-no swap-[1, 3, 4, 2] 3. Compare 4 and 2-swap-[1, 3, 2, 4]

Mistake 2: Binary Search on an Unsorted List - Prompt: Use Binary Search to find 7 in [5, 2, 9, 1, 7]. - Common Wrong Response: 1. Check the middle number (9). 9 > 7, so search the left half-[5, 2]. 2. Check the middle number (5). 5 < 7, so search the right half-[2]. 3. 2-7, so 7 isn’t in the list. - Why It Loses Credit: Binary Search only works on sorted lists. The student didn’t sort the list first, so the algorithm fails. - Correct Approach: 1. Sort the list-[1, 2, 5, 7, 9]. 2. Check the middle number (5). 5 < 7, so search the right half-[7, 9]. 3. Check the middle number (7). Found it!

Mistake 3: Confusing Efficiency with Speed - Prompt: Which is more efficient: Bubble Sort or Binary Search? - Common Wrong Response: “Binary Search is more efficient because it’s faster.” - Why It Loses Credit: The student didn’t explain why Binary Search is faster (fewer steps) or acknowledge that Bubble Sort is a sorting algorithm, not a searching one. - Correct Approach: - Binary Search is more efficient for searching because it takes at most log?(n) steps (e.g., 7 steps for 100 items), while Linear Search takes n steps (100 steps for 100 items). - Bubble Sort is inefficient for sorting because it takes n² steps (e.g., 10,000 steps for 100 items).

5. Connection Layer

1. Within Computer Science: Algorithms-Data Structures — Sorting and searching are why we use data structures like arrays and trees. A binary search tree is literally a tree where each “branch” splits the data in half, just like Binary Search.
2. Across Subjects: Algorithms-Math (Logarithms) — Binary Search’s efficiency (log?(n)) is why logarithms matter. If you have 1,000,000 items, Binary Search takes at most 20 steps (log?(1,000,000)-20), while Linear Search could take 1,000,000 steps.
3. Outside School: Algorithms-Spotify Playlists — When you sort your playlist by “Most Played,” Spotify uses a sorting algorithm. When you search for a song, it uses a search algorithm to find it fast—even if you have 10,000 songs.

6. The Stretch Question

"If you have a list of 1,000,000 names and you need to find one specific name, Binary Search is way faster than Linear Search. But what if the list is constantly changing—like a live leaderboard in a video game—where names are being added and removed all the time? Would Binary Search still be the best choice? Why or why not?"

Pointer Toward the Answer: Binary Search is fast only if the list is sorted, but sorting a list of 1,000,000 names takes time (especially if it’s changing constantly). In this case, a hash table (a different data structure) might be better because it lets you find a name in one step, no sorting required. But hash tables use more memory, so it’s a trade-off: speed vs. space. This is why computer scientists are always asking, “What’s the best algorithm for this specific problem?”