Search & Sort Algorithms
Standard algorithms are the bread and butter of computer science. You must understand the visual mechanics of Linear and Binary searches, alongside Bubble, Merge, and Insertion sorts.
1. Searching Algorithms
Linear Search
- Mechanics: Starts at the very first item and systematically checks each item one-by-one until the target is found or the end of the list is reached.
- Pre-requisite: None. It works perfectly on unsorted lists.
- Drawback: Very slow on large datasets (e.g. searching 1 million items might take 1 million checks).
Binary Search
- Mechanics: Calculates the middle item. If it is the target, it stops. If the target is smaller, it discards the right half. If the target is larger, it discards the left half. Repeats until found.
- Drawback: It cannot work on mixed up data.
Examiner's Eye - The Binary Search Trap!
If an exam asks you to "State the steps required to perform a Binary Search", your absolute first step MUST be: "Sort the list / Check if the list is sorted". If you do not state this explicitly, you will drop marks immediately.
2. Sorting Algorithms
Watch how standard algorithms swap items step-by-step.
Dataset
Bubble Sort
Compares adjacent pairs of items. If they are in the wrong order, it swaps them. It passes through the entire list multiple times until a full pass is completed with zero swaps.
Insertion Sort
Splits the list into a 'sorted' and 'unsorted' side. It takes the first item from the unsorted side and inserts it into its exact correct position in the sorted side.
Merge Sort
A 'divide and conquer' algorithm. It divides the list in half repeatedly until each list contains only one item. It then merges them back together in pairs, sorting them as they are merged, until a single sorted list remains.
Check Your Understanding
1. You have an unordered list of 5,000 player names in a game. Which searching algorithm MUST be used to find a specific name?
2. Which algorithm uses a 'divide and conquer' methodology, breaking a list down into sub-lists of one before rebuilding it?
Written Exam Scenario (AO2/AO3)
Stretch (Grade 9)"A teacher wants to find a specific student's grade in an unsorted list of 500 test scores. State which standard searching algorithm must be used and explain why the other standard search cannot work." (3 marks)
Target Algorithm: The teacher MUST use a Linear Search.
Explanation: A Binary Search relies on finding the middle value and discarding half of the list based on whether the target is larger or smaller. Because the list is completely unsorted, discarding a half would accidentally discard valid data, meaning Binary Search cannot function here.