Introduction to Searching and Sorting
Welcome! In this chapter, we are going to look at the "bread and butter" of computer science: Searching and Sorting. Whether you are scrolling through your contacts to find a friend's name or a website is showing you products from cheapest to most expensive, these algorithms are working behind the scenes.
Don't worry if these sound intimidating at first. We will break each one down using everyday analogies. By the end of this, you’ll understand how computers find and organize data efficiently. This content is a core part of Theme B: Computational thinking and problem-solving and is essential for your Paper 2 exam.
Note: Before starting, make sure you are comfortable with "Arrays, collections and strings," as we will be using these to store the data we search and sort.
1. Searching Algorithms
Searching is the process of finding a specific target value within a collection of data. In the IB curriculum, you need to know two main types: Linear Search and Binary Search.
Linear Search (Sequential Search)
The Linear Search is the most straightforward way to find something. It starts at the very beginning of a list and checks every single item one by one until it finds a match or reaches the end.
The Analogy: Imagine you are looking for a specific book on a messy shelf. You start at the far left and look at every title, one after another, until you find the book you want.
How it works step-by-step:
1. Start at the first element (index \( 0 \)).
2. Compare the current element with the target value.
3. If they match, you're done! Return the position.
4. If they don't match, move to the next element.
5. Repeat until the target is found or you run out of items.
Efficiency: In the worst-case scenario (where the item is at the very end or not there at all), if there are \( n \) items, the computer makes \( n \) comparisons. We call this \( O(n) \) complexity.
Quick Tip: Linear search is the only option if your data is unsorted.
Binary Search
Binary Search is a much faster method, but it has one strict rule: The data MUST be sorted (e.g., in alphabetical or numerical order) before you start.
The Analogy: Think of a physical dictionary. If you're looking for the word "Python," you don't start at page 1. You open to the middle. If you see words starting with "M," you know "Python" must be in the second half. You just ignored half the book in one second!
How it works step-by-step:
1. Find the middle element of the list.
2. Compare the middle element to your target.
3. If it's a match, stop.
4. If your target is smaller than the middle, throw away the right half and repeat the search on the left half.
5. If your target is larger than the middle, throw away the left half and repeat on the right half.
6. Keep dividing until the item is found.
Efficiency: Because we cut the data in half every time, it is incredibly fast. For \( n \) items, it takes roughly \( \log_{2}(n) \) steps. We call this \( O(\log n) \).
Common Mistake: Forgetting to check if the list is sorted. If you try a Binary Search on an unsorted list, it will give you the wrong answer!
2. Sorting Algorithms
Sorting is the process of arranging data into a logical order (like smallest to largest). We will look at three classic algorithms: Bubble Sort, Selection Sort, and Insertion Sort.
Bubble Sort
This is often the first sorting algorithm students learn. It’s called "Bubble" sort because the largest values gradually "bubble up" to the end of the list.
The Analogy: Imagine several people of different heights standing in a line. You compare the first two. If the one on the left is taller, they swap places. Then you compare the 2nd and 3rd person, swapping if necessary. By the time you reach the end of the line, the tallest person is guaranteed to be at the far right.
How it works:
1. Compare adjacent pairs of items.
2. If they are in the wrong order, swap them.
3. Repeat this for the whole list.
4. After one full pass, the largest item is in the correct spot. Repeat the process for the remaining items.
Key Takeaway: Bubble sort is easy to write but very slow for large amounts of data. Its efficiency is \( O(n^2) \).
Selection Sort
Selection sort is more systematic. It "selects" the smallest item and puts it at the beginning.
The Analogy: You have a pile of cards on a table. You scan the whole pile to find the lowest card, pick it up, and start a new "sorted" pile. You look at the remaining cards, find the next lowest, and add it to your new pile.
How it works:
1. Find the smallest item in the unsorted part of the list.
2. Swap it with the item at the current starting position.
3. Move the "starting position" one step to the right.
4. Repeat until the whole list is processed.
Key Takeaway: Selection sort performs the same number of comparisons regardless of whether the list is already partially sorted. Its efficiency is also \( O(n^2) \).
Insertion Sort
Insertion sort works the way most people naturally sort a hand of playing cards.
The Analogy: You hold your cards in a pile. You take one card at a time and insert it into its correct position relative to the cards you are already holding.
How it works:
1. Assume the first item is already "sorted."
2. Take the next item (the "key").
3. Compare the key with the items to its left.
4. Shift the larger items to the right to make a gap.
5. Insert the key into its correct spot.
6. Repeat for all items.
Did you know? Insertion sort is actually very fast for lists that are already "nearly sorted." Like the others, its worst-case efficiency is \( O(n^2) \).
3. Comparing Algorithms
In the exam, you might be asked to evaluate which algorithm is best for a specific scenario. Here is a quick reference table:
Linear Search: Best for small lists or unsorted data. Simple to code.
Binary Search: Best for large, sorted datasets. Much faster than Linear.
Bubble Sort: Generally inefficient; used mostly for educational purposes.
Selection Sort: Good when memory swaps are expensive, but generally slow.
Insertion Sort: Efficient for small datasets or data that is already mostly sorted.
Quick Review Box:
- Searching: Finding an item.
- Sorting: Ordering items.
- Must be sorted: Only Binary Search requires this!
- Big O: A way to measure how the time taken grows as the list size (\( n \)) increases.
Final Tips for Success
1. Trace the code: When practicing, try "dry running" these algorithms on paper with a small list of 5 numbers. It’s the best way to understand the swaps and comparisons.
2. Identify the loops: Notice that all three sorting algorithms use nested loops (a loop inside a loop). This is why they have \( n \times n \), or \( n^2 \), complexity.
3. Don't panic: If a question asks you to write one of these in Python or Java, remember the core logic first. The syntax is just the "translation" of the logic you already know.