Understand and apply standard search and sort algorithms (e.g. linear search, bubble sort)

Algorithm Design and Problem‑Solving 📚

1. What is an Algorithm?

An algorithm is a step‑by‑step recipe that tells a computer exactly how to solve a problem. Think of it as a cooking recipe: you need a list of ingredients (data), a set of instructions (steps), and a final dish (output). In computer science, the “ingredients” are usually numbers or words, and the “dish” is the result you want, like a sorted list or a found item.

2. Search Algorithms: Linear Search 🔍

Linear search is the simplest way to find an item in a list. Imagine you’re looking for your favourite book in a stack of unsorted books. You start at the top and check each book one by one until you find it or run out of books.

Algorithm Steps

1. Start at the first element of the list.
2. Compare the current element with the target value.
3. If it matches, return the index (or the element itself).
4. If it doesn’t match, move to the next element.
5. Repeat until the end of the list is reached.
6. If the target is not found, return “not found”.

Pseudocode

function linearSearch(list, target):
    for i from 0 to length(list)-1:
        if list[i] == target:
            return i
    return -1

Time Complexity

The worst‑case time is proportional to the number of elements, so we write it as $O(n)$.

3. Sort Algorithms: Bubble Sort 🔄

Bubble sort is a gentle way to arrange items, like arranging a line of books by height. Each pass “bubbles” the tallest book to the end, just like a bubble rises to the surface of water.

Algorithm Steps

1. Start at the first element of the list.
2. Compare the current element with the next one.
3. If the current element is larger, swap them.
4. Move to the next pair and repeat until the end of the list.
5. After one full pass, the largest element is at the end.
6. Repeat the whole process for the remaining unsorted part.
7. Stop when no swaps are needed in a pass.

Pseudocode

function bubbleSort(list):
    n = length(list)
    for i from 0 to n-1:
        swapped = false
        for j from 0 to n-i-2:
            if list[j] > list[j+1]:
                swap(list[j], list[j+1])
                swapped = true
        if not swapped:
            break

Illustration of Passes

Time Complexity

In the worst case, bubble sort performs about $n^2$ comparisons, so its time complexity is $O(n^2)$. It’s simple but not efficient for large lists.

4. Problem‑Solving Tips 🧩

• Understand the problem: Write down what you’re given and what you need to find.
• Plan a strategy: Choose an algorithm that fits the data size and required speed.
• Write pseudocode: Outline the steps before coding.
• Test with examples: Use small lists to check each step.
• Analyze complexity: Estimate how the algorithm scales with larger inputs.

5. Quick Recap 📌

• Linear search: $O(n)$ time, great for small or unsorted lists.
• Bubble sort: $O(n^2)$ time, easy to understand but slow for big data.
• Always choose the right tool for the problem size and constraints.