← VCE Software Development U3O1

Comparing searching and sorting algorithms

How many steps an algorithm takes as data grows, and what it needs (e.g. sorted data for binary search). Compare it to choose between linear or binary search, selection or quick sort.

Part of: VCE Software Development - U3O1 - Programming — Module 156, QCE Digital Solutions Unit 1 — Programmed Solutions — Module 104, WA Computer Science ATAR Year 11 — Standard Algorithms — Module 37

Understanding Comparing searching and sorting algorithms in VCE Software Development U3O1

What it does: Nested loops over the data show selection sort's n x n growth. Doubling the data roughly quadruples the steps. Partitioning values around a pivot splits the problem into smaller parts, which is why quick sort is fast on average. A poor pivot choice gives its worst case. Binary search halves the search area by comparing with the middle item, so the data must already be in order. Linear search works on unsorted data. Sorting costs more steps than one linear scan. Sorting first only pays off if you will search the list many times. A very unbalanced split leaves almost all items on one side, so the partitioning has to be repeated many times. Even splits give the best performance.

Common mistakes: A function header must end with a colon. It should be def linear(items, goal): so the step-counting linear search can run. The best case for linear search is when the target is the first item, which takes 1 step. len(data) steps is the worst case. It should be best_steps = 1.

Class: _____________________  ·  Name: _____________________  ·  Date: _________

Free printable worksheet with full answer key — or add this module to a class and your students practise it interactively.

🖨 Print worksheet + answer key Add Comparing searching and sorting algorithms to a class →

This module's key terms are also in a printable crossword (Modules 156–166) and word search (Modules 142–166).

Take this worksheet further — free with Cloodit

Each concept is reinforced from every angle — learned, then applied, then tested.

Learning
Duo
Which search algorithm needs the data to be sorted before it can work?
Binary searchLinear search
Matches
data = [9, 2, 7, 4] binary_search(data, 7)
↓
Binary search is used on unsorted data. It only works correctly if the list is sorted first, so sort it or use linear search.
Applying
Meanings
Term
algorithm efficiency
Meaning
How many steps an algorithm takes as data grows, and what it needs (e.g. sorted data for binary search). Compare it to choose between linear or binary search, selection or quick sort.
Practice
import math
Testing
Gaps
data = (data)
Check Answer
Spots
1def linear(items, goal)
2 steps = 0

Cloodit turns curriculum-aligned coding content into journeys students work through one biome at a time.

The 'Hermit Crab' badge — Definition Collector, one of Cloodit's 106 collectible badges
Students earn collectable badges

Over 100 of them, across seven natural biomes.

Study Buddy
Students build a real study resource

Turns their work into revision material ready for Flash Cards and Exam study.

Diamond Dash — one of Cloodit's live, competitive Sprint games
Students lock in with Sprints

Live, competitive practice for the start of the lesson or a teacher-led lesson finisher.

A Cloodit certificate of achievement, ready to personalise and print
Custom printable certificates

Honour your top performers, or encourage a student who's trying hard — ready to print in seconds.

Add to class →

Quick Questions

1. Which search algorithm needs the data to be sorted before it can work?
A. Binary search ✓
B. Linear search
Binary search halves the search area by comparing with the middle item, so the data must already be in order. Linear search works on unsorted data.
2. A list has 1,000,000 sorted items. Which search takes far fewer steps in the worst case?
A. Binary search (about 20 steps) ✓
B. Linear search (about 20 steps)
Binary search halves the data each step, so about 20 checks cover a million items. Linear search could need up to 1,000,000 checks.
3. What is the best case for a linear search?
A. The target is the last item in the list
B. The target is the first item in the list ✓
If the first item matches, linear search finishes after one comparison. The last item (or a missing target) is the worst case.
4. You must search an unsorted list just once. Which is usually the better choice?
A. Linear search ✓
B. Sort the list, then use binary search
Sorting costs more steps than one linear scan. Sorting first only pays off if you will search the list many times.
5. Which statement about selection sort and quick sort is correct for large lists?
A. Selection sort is usually faster on average
B. Quick sort is usually faster on average ✓
Selection sort compares every remaining item on each pass, so its steps grow quickly with the data. Quick sort partitions around a pivot and is usually much faster.

Match the Pairs

for item in data: if item == target: → Linear search: checks items one at a time, so up to n steps for n items, and works on unsorted data
mid = (low + high) // 2 → Binary search: halves the search range each step, so it needs very few steps but the data must be sorted
Selection sort takes about n x n steps in every case, because it scans the unsorted part to find the minimum for each position → for i in range(n): for j in range(i + 1, n):
Quick sort is usually much faster on large data because it splits the list around a pivot, but its worst case (a bad pivot) is slow → left = [x for x in data if x < pivot]
data = [9, 2, 7, 4] binary_search(data, 7) → Binary search is used on unsorted data. It only works correctly if the list is sorted first, so sort it or use linear search.
# Best case for linear search: # target is the last item → The best case for linear search is when the target is the first item (1 step). The last item (or a missing target) is the worst case, needing n steps.

Key Term

algorithm efficiency
How many steps an algorithm takes as data grows, and what it needs (e.g. sorted data for binary search). Compare it to choose between linear or binary search, selection or quick sort.

Fill in the Blanks

1. data = [9, 2, 7, 4] data = sorted(data) index = binary_search(data, 7)
Hint: Type the built-in function that puts the list in order, which binary search needs before it can run
2. worst = len(data) print(worst)
Hint: Type the function that counts how many items the list holds, which is the worst case for linear search
3. best = 1 print(best)
Hint: Type the number of comparisons needed in the best case, when the target is the first item checked
4. n = len(data) steps = n ** 2
Hint: Type the Python operator that raises a number to a power, showing how quickly selection sort steps grow
5. if data == sorted(data): index = binary_search(data, 7) else: index = linear_search(data, 7)
Hint: Type the keyword that starts a decision, used to pick binary search only when the data is already in order

Spot the Error

Question 1
A def linear(items, goal)
B steps = 0
C for x in items:
D steps += 1
E if x == goal:
F return steps
Line A — A function header must end with a colon. It should be def linear(items, goal): so the step-counting linear search can run.
Question 2
A data = [8, 3, 6, 1]
B target = 8
C best_steps = len(data)
D print(best_steps)
Line C — The best case for linear search is when the target is the first item, which takes 1 step. len(data) steps is the worst case. It should be best_steps = 1.
Question 3
A data = [9, 4, 7, 2, 5]
B data.reverse()
C low = 0
D high = len(data) - 1
Line B — Binary search needs sorted data. reverse() only flips the order and does not sort it. It should be data.sort() before searching.
Question 4
A names = ['Zoe', 'Ava', 'Leo'
B n = len(names)
C comparisons = n * (n - 1) // 2
D print(comparisons)
Line A — The list is missing its closing square bracket. It should end with ] so the data can be used to count selection sort comparisons.
Question 5
A def quick(items):
B if len(items) >= 1:
C return items
D pivot = items[0]
E # partition around pivot
Line B — The base case should stop when there is 1 item or fewer (<= 1). With >= 1 every non-empty list is returned unsorted. It should be if len(items) <= 1:.

Student with a class code? Join your class →