Welcome to Algorithm Classification!

Hello there! In this chapter, we are going to explore how Computer Scientists "score" and group different algorithms. Think of an algorithm as a recipe: some recipes are quick but messy, while others take time but produce perfect results. By the end of these notes, you’ll be able to look at two different ways of solving a problem and decide which one is the "winner" based on its efficiency.

Don't worry if this seems tricky at first! We are basically just learning how to compare tools to see which one works best for a specific job.

1. What Makes a "Good" Algorithm?

Before we classify them, we need to know what we are looking for. According to our syllabus, we evaluate a computer system (and its algorithms) based on three main things:

  • Correctness: Does it actually solve the problem and give the right answer?
  • Efficiency: How fast does it run (Time Efficiency) and how much memory does it use (Space Efficiency)?
  • Maintainability: Is the code easy for another human to read and fix later?

The Efficiency Trade-off

In Computer Science, we often have to choose between speed and memory. This is like moving to a new house: you can use a small car and take 20 trips (low memory use, but takes a long time) or hire a giant truck and do it in 1 trip (uses lots of "space," but is very fast).

Quick Review: The Evaluation Criteria

Just remember CEM:
C - Correctness (Does it work?)
E - Efficiency (Is it fast/small?)
M - Maintainability (Can I read it?)

2. Classifying Searching Algorithms

Searching is finding a specific item in a list. We focus on two main types: Linear Search and Binary Search.

Linear Search

This is the "simplest" search. You start at the beginning of a list and check every single item until you find what you’re looking for or reach the end.

  • Efficiency: Generally low. If your item is at the very end of a list of a million items, you have to look a million times!
  • Condition: It works on any list (ordered or unordered).

Binary Search

This is a much smarter "Divide and Conquer" algorithm. It goes to the middle of the list, decides if the item is in the top half or bottom half, and throws away the half it doesn't need. It repeats this until the item is found.

  • Efficiency: Very high. It finds items much faster than Linear Search as the list gets bigger.
  • Condition: The list MUST be ordered (sorted) first.

Analogy: Imagine looking for a word in a dictionary. A Linear Search would be reading every single word starting from 'A'. A Binary Search is opening the book in the middle, seeing if your word comes before or after that page, and flipping accordingly.

Common Mistake to Avoid

Don't forget: You cannot use a Binary Search on a messy, unsorted list. If the list isn't in order, you are stuck using Linear Search.

Key Takeaway: Use Linear Search for small or messy lists. Use Binary Search for large, sorted lists for better time efficiency.

3. Classifying Sorting Algorithms

Sorting is putting a messy list into order (like alphabetically or from smallest to largest). We look at Bubble Sort and Merge Sort.

Bubble Sort

This algorithm goes through the list in "passes." It compares two items side-by-side and swaps them if they are in the wrong order. The largest items "bubble up" to the end of the list.

  • Time Efficiency: Generally very inefficient and slow for large lists.
  • Memory Efficiency: Very good, as it sorts the list "in place" without needing extra workspace.
  • Did you know? An efficient version of Bubble Sort can stop early if it makes a full pass without swapping anything—this means the list is already sorted!

Merge Sort

This is a more complex algorithm. It chops the list into tiny pieces (individual items) and then merges them back together in the correct order.

  • Time Efficiency: Much faster than Bubble Sort for large amounts of data.
  • Memory Efficiency: Lower than Bubble Sort because it needs extra memory to store the "chopped up" pieces while it works.

Step-by-Step Comparison

To decide which one to use, look at these factors:

  1. How much data is there? For huge lists, Merge Sort wins on speed.
  2. How much memory do you have? If memory is very tight (like on a tiny microchip), Bubble Sort might be better.
  3. Is the list already partially sorted? Bubble Sort can be quite fast if the list is nearly finished, whereas Merge Sort takes roughly the same time no matter what.
Memory Aid: Sorting Summary

"Bubble is Basic (and slow), Merge is Mighty (and fast)!"

Key Takeaway: Bubble Sort is easy to write but slow. Merge Sort is fast for big data but uses more memory.

4. Summary Table for Revision

Use this table to quickly compare the algorithms we've covered:

Algorithm Type Main Advantage Main Disadvantage
Linear Search Searching Works on unsorted data. Slow on large lists.
Binary Search Searching Extremely fast. Data must be sorted first.
Bubble Sort Sorting Uses very little memory. Very slow for large lists.
Merge Sort Sorting Very fast for large lists. Uses more memory.

Final Tip: When the exam asks you to compare algorithms, always mention Time Efficiency (speed) and the initial state of the data (Is it sorted? Is it a huge list?).