Introduction to Searching & Sorting Algorithms

In Computer Science, we often need to find a specific piece of information or organize data into a particular order. To do this efficiently, we use standard algorithms. Think of an algorithm as a "recipe" or a set of step-by-step instructions that a computer follows to complete a task.

In this chapter, we will look at two ways to find data (Linear Search and Binary Search) and two ways to organize data (Bubble Sort and Merge Sort). Understanding these is a core part of Problem Solving.

Note: This chapter focuses on how these algorithms work. To learn how to measure their speed or compare them in detail, see the chapter on "Evaluating algorithm efficiency".

1. Searching Algorithms

Searching is the process of looking for a specific item (the target) within a collection of data, such as an array.

A. Linear Search

This is the simplest way to search. It starts at the very beginning of a list and looks at every single item, one by one, until it finds what it is looking for or reaches the end.

The Analogy: Imagine you are looking for a specific book on a messy shelf. You start at the left and check every book until you find the right one.

How it works (Step-by-Step):

  1. Start at the first item in the list (\(index = 0\)).
  2. Compare the current item with the target value.
  3. If they are the same, the search is successful! You have found the item.
  4. If they are different, move to the next item in the list.
  5. Repeat steps 2–4 until you find the item or reach the end of the list.

Key Fact: Linear search works on any list, whether the items are in order or completely jumbled up.

B. Binary Search

Binary search is much faster than linear search, but there is a catch: the list must be sorted first (e.g., in alphabetical order or from smallest to largest number).

The Analogy: Imagine looking for a word in a physical dictionary. You don't start at page 1. You open it in the middle. If your word comes "after" the middle page, you ignore the first half of the book and repeat the process with the second half.

How it works (Step-by-Step):

  1. Find the middle item in the sorted list.
  2. Compare the middle item with your target.
  3. If the middle item is the target, you are done!
  4. If the target is smaller than the middle item, throw away the right half of the list.
  5. If the target is larger than the middle item, throw away the left half of the list.
  6. Repeat the process with the remaining half until the item is found.

Quick Review:
Linear Search: Works on any list; checks one by one.
Binary Search: Only works on sorted lists; halves the data each time.

2. Sorting Algorithms

Sorting means putting data into a specific order (usually ascending, like \(1, 2, 3...\) or \(A, B, C...\)).

A. Bubble Sort

Bubble sort is a simple algorithm that steps through the list multiple times. It compares neighboring items and swaps them if they are in the wrong order.

The Analogy: Think of the "heavier" (larger) numbers sinking to the bottom, while the "lighter" (smaller) numbers "bubble up" to the top.

How it works (Step-by-Step):

  1. Start at the beginning of the list.
  2. Compare the first two items. If the first is bigger than the second, swap them.
  3. Move to the next pair (2nd and 3rd items) and repeat the comparison/swap.
  4. Continue until you reach the end of the list. (The largest item is now at the very end).
  5. Repeat the whole process for the rest of the items until no more swaps are needed.

Common Mistake: Students often forget that Bubble Sort usually requires multiple "passes" through the list. One pass is rarely enough to sort everything!

B. Merge Sort

Merge sort is a "divide and conquer" algorithm. It is more complex than Bubble Sort but is much faster for large amounts of data.

How it works (Step-by-Step):

  1. Divide: Split the unsorted list in half. Keep splitting the resulting lists until every list contains only one item. (A list with one item is technically "sorted").
  2. Conquer (Merge): Merge the small lists back together. As you merge them, put the items in the correct order.
  3. Repeat the merging process until you have one single, fully sorted list.

Did you know? Merge sort is very consistent. Whether the data is already nearly sorted or completely random, it follows the same steps and performs reliably.

3. Summary Table: Choosing the Right Algorithm

The choice of algorithm depends on the data structures and values you are working with.

Algorithm Type Main Requirement Best Used When...
Linear Search Search None The list is small or unsorted.
Binary Search Search List must be sorted The list is large and already ordered.
Bubble Sort Sort None The list is small; you want a simple program.
Merge Sort Sort None The list is large; speed is important.

Key Takeaways

  • Searching finds a value; Sorting organizes values.
  • Binary Search is fast but requires sorted data.
  • Bubble Sort is easy to understand but can be slow because it only swaps adjacent items.
  • Merge Sort uses a divide and conquer approach, making it very efficient for big datasets.
  • Don't worry if these seem tricky at first! Try practicing with a deck of cards to see how the swaps (Bubble) or splits (Merge) work in real life.