Comparing searching and sorting algorithms

Name:

Date:

Class:

Quick Questions

Shade in the A or B circle for each question.

1. Which search algorithm needs the data to be sorted before it can work?

A Binary search

B Linear search

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)

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

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

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

Match the Pairs

Draw a line connecting each item on the left to its match on the right.

Left column		Right column
1for item in data: if item == target:		ABinary search: halves the search range each step, so it needs very few steps but the data must be sorted
2mid = (low + high) // 2		BLinear search: checks items one at a time, so up to n steps for n items, and works on unsorted data
3Selection sort takes about n x n steps in every case, because it scans the unsorted part to find the minimum for each position		Cfor i in range(n): for j in range(i + 1, n):
4Quick 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		DBinary search is used on unsorted data. It only works correctly if the list is sorted first, so sort it or use linear search.
5data = [9, 2, 7, 4] binary_search(data, 7)		EThe 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.
6# Best case for linear search: # target is the last item		Fleft = [x for x in data if x < pivot]

Definitions

algorithm efficiency

Fill in the Blanks

Complete each line of code by filling in the missing parts.

data = [9, 2, 7, 4] data = ______(data) index = binary_search(data, 7)

worst = ___(data) print(worst)

best = _ print(best)

n = len(data) steps = n __ 2

__ data == sorted(data): index = binary_search(data, 7) else: index = linear_search(data, 7)

Spot the Error

Shade in the letter of the line that contains an 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

Question 2

A data = [8, 3, 6, 1]

B target = 8

C best_steps = len(data)

D print(best_steps)

Question 3

A data = [9, 4, 7, 2, 5]

B data.reverse()

C low = 0

D high = len(data) - 1

Question 4

A names = ['Zoe', 'Ava', 'Leo'

B n = len(names)

C comparisons = n * (n - 1) // 2

D print(comparisons)

Question 5

A def quick(items):

B if len(items) >= 1:

C return items

D pivot = items[0]

E # partition around pivot

Answer Key

Comparing searching and sorting algorithms

Section A: Quick Questions

A — Binary search

A — Binary search (about 20 steps)

B — The target is the first item in the list

A — Linear search

B — Quick sort is usually faster on average

Section B: 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.

Section C: Definitions

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.

Section D: Fill in the Blanks

data = [9, 2, 7, 4]
data = sorted(data)
index = binary_search(data, 7)

worst = len(data)
print(worst)

best = 1
print(best)

n = len(data)
steps = n ** 2

if data == sorted(data):
    index = binary_search(data, 7)
else: index = linear_search(data, 7)

Section E: Spot the Error

A — A function header must end with a colon. It should be def linear(items, goal): so the step-counting linear search can run.

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.

B — Binary search needs sorted data. reverse() only flips the order and does not sort it. It should be data.sort() before searching.

A — The list is missing its closing square bracket. It should end with ] so the data can be used to count selection sort comparisons.

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:.