VCE Vault

Year 8 Digital Technologies · Creating Digital Solutions · 10m read

Advanced Algorithms — Searching and Sorting

Ever wondered how your phone finds a contact in milliseconds, or how Netflix organises thousands of shows? Behind the scenes, searching and sorting algorithms are doing the heavy lifting. You'll learn how different techniques like binary search and bubble sort actually work—tracing through them step by step—so you understand why some methods are lightning-fast while others are slower. This knowledge is essential for VCE computing and gives you real insight into how every app you use operates under the hood.

Learning objective: Describe and trace linear/binary search and bubble/selection sort algorithms.

By the end of this lesson you can:

  • I trace a linear search and binary search and compare their efficiency.
  • I trace a bubble sort and selection sort.
  • I explain what Big O notation means for algorithm efficiency.

Searching is finding a word in a dictionary. Linear search reads every page; binary search opens the middle and halves the search each time — much faster on sorted data.

Search and sort algorithms

SEARCHING ALGORITHMS:

LINEAR SEARCH:
Check EACH element one by one until found or end of list.
Best case: 1 comparison (target is first).
Worst case: n comparisons (target is last or not found).
Works on: any list, sorted or unsorted.
Efficiency: O(n) — proportional to list size.

BINARY SEARCH:
Works ONLY on SORTED lists.
1. Start at the MIDDLE.
2. If target < middle → search left half.
3. If target > middle → search right half.
4. Repeat until found or list empty.
Each step HALVES the remaining list.
Efficiency: O(log n) — dramatically faster for large datasets.
List of 1 million items: linear = up to 1 000 000 steps. Binary = up to 20 steps.

SORTING ALGORITHMS:

BUBBLE SORT:
Repeatedly compare adjacent pairs. Swap if out of order. Repeat passes until no swaps needed.
Each pass "bubbles" the largest unsorted element to the end.
Passes needed: at most n-1. Comparisons: up to n²/2.
Efficiency: O(n²) — slow for large data.
Simple to implement and understand.

SELECTION SORT:
Find the MINIMUM element. Put it at the start. Repeat for remaining unsorted portion.
n-1 passes needed. Always exactly n²/2 comparisons.
Also O(n²) but fewer swaps than bubble sort.

BIG O NOTATION (algorithm efficiency):
O(1): constant time — same speed regardless of input size. (Array access by index)
O(log n): logarithmic — binary search. Excellent for large data.
O(n): linear — linear search. Proportional to input size.
O(n²): quadratic — bubble/selection sort. Becomes very slow for large data.

Algorithm efficiency rules

  • Binary search requires sorted data: Binary search ONLY works if the data is sorted. If you sort first then binary search, the combined cost might exceed a simple linear search for small datasets.
  • O(n²) is very slow for large data: 1000 items: O(n²) = ~500 000 operations. 1 000 000 items: O(n²) = 500 billion operations. This is why better algorithms matter enormously at scale.
  • Trace = write step by step: In algorithm tracing, write out the state of the list after EVERY pass or comparison. Markers check each step.

Quick reference

| Algorithm | Idea | Speed |
|---|---|---|
| Linear search | Check each item | Slow on big lists |
| Binary search | Halve sorted list | Fast |
| Bubble sort | Swap neighbours | Slow |
| Selection sort | Pick smallest each pass | Slow |
| Merge sort | Divide and merge | Fast |

Worked example (Medium)

Trace a binary search for target = 17 in sorted list: [4, 9, 12, 17, 23, 31, 45]

  1. Step 1: Find middle. List has 7 items. Middle index = 3. Middle value = 17.
  2. Compare. Target (17) = Middle (17). FOUND in 1 comparison!
  3. Efficiency. Best case: found at middle immediately. Worst case: 3 comparisons (7 items → 4 → 2 → 1).

Answer: Found in 1 step: [4, 9, 12, ►17◄, 23, 31, 45] — middle element is the target.

Worked example (Hard)

Trace a COMPLETE selection sort on: [29, 10, 14, 37, 13]. Show the list state after each pass.

  1. Pass 1: find minimum of [29,10,14,37,13]. Minimum = 10 (index 1). Swap with position 0. List: [10, 29, 14, 37, 13]. Sorted region: [10].
  2. Pass 2: find minimum of [29,14,37,13]. Minimum = 13 (index 4). Swap with position 1. List: [10, 13, 14, 37, 29]. Sorted region: [10, 13].
  3. Pass 3: find minimum of [14,37,29]. Minimum = 14 (already at position 2). No swap needed. List: [10, 13, 14, 37, 29]. Sorted region: [10, 13, 14].
  4. Pass 4: find minimum of [37,29]. Minimum = 29 (index 4). Swap with position 3. List: [10, 13, 14, 29, 37]. Sorted. 4 passes for 5 elements (n-1 passes).

Answer: After pass 1: [10,29,14,37,13]. Pass 2: [10,13,14,37,29]. Pass 3: [10,13,14,37,29]. Pass 4: [10,13,14,29,37]. Sorted in 4 passes.

Common mistakes

  • Trying binary search on an unsorted list Binary search relies on the list being sorted to determine which half to eliminate. On an unsorted list, checking the middle tells you nothing about where the target might be. Fix: Always check: is the data sorted? If not, sort first or use linear search.
  • Not showing every step in a trace Algorithm tracing marks are awarded per step. Skipping steps means skipping marks — even if the final answer is correct. Fix: Write the list state after EVERY comparison and swap. Use a table format with columns for each pass.
  • Confusing bubble sort and selection sort Both are O(n²), but they work differently. Bubble sort compares adjacent pairs; selection sort finds the minimum and places it. Fix: Bubble sort: adjacent swaps, largest "bubbles" to end. Selection sort: find minimum, place it at start of unsorted section.

Why O(n log n) algorithms changed computing

Bubble sort and selection sort are both O(n²) — for 1 million items, that's roughly 500 billion operations. Even on a fast computer, this takes hours. For decades, this was a real bottleneck.

Then algorithms like merge sort and quicksort achieved O(n log n) — for 1 million items, that's only about 20 million operations. That's 25 000 times faster! This isn't a small improvement; it's the difference between "takes days" and "takes milliseconds."

Merge sort works by dividing the list in half repeatedly (log n divisions), then merging sorted halves back together (n comparisons per merge level). The divide-and-conquer strategy is a fundamental algorithm design pattern used far beyond sorting.

Mathematically, it's been proven that no comparison-based sorting algorithm can do better than O(n log n) in the average case. This means merge sort and quicksort are essentially optimal. Understanding Big O notation helps you choose the right algorithm — the difference between O(n²) and O(n log n) can mean the difference between a program that runs in seconds and one that never finishes.

Practice questions

  1. Binary search can only be performed on:

    1. Any list of numbers
    2. A sorted list
    3. A list of strings
    4. A list with no duplicates

    (1 marks)

  2. Trace ONE pass of bubble sort on: [5, 3, 8, 1, 9]. Show each comparison and swap.

    (2 marks)

Summary

  • Trace a linear search and binary search and compare their efficiency.
  • Trace a bubble sort and selection sort.
  • Explain what Big O notation means for algorithm efficiency.

More from Year 8 Digital Technologies