Quick sort in Python

Name:

Date:

Class:

Quick Questions

Shade in the A or B circle for each question.

1. Which base case correctly stops quick_sort(items) from recursing forever?

A if len(items) >= 1: return items

B if len(items) <= 1: return items

2. Which return line joins the sorted parts in the correct order?

A return quick_sort(larger) + equal + quick_sort(smaller)

B return quick_sort(smaller) + equal + quick_sort(larger)

3. Given pivot = 5 and items = [7, 2, 5, 9, 1], which list should smaller hold?

A [2, 1]

B [2, 5, 1]

4. Which line builds the larger list correctly?

A larger = [x for x in items if x > pivot]

B larger = [x for x in items if x >= pivot]

5. Why does quick_sort keep an equal list as well as smaller and larger?

A So duplicates of the pivot are kept and not sorted again

B So the pivot can be deleted from the sorted result

Match the Pairs

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

Left column		Right column
1if len(items) <= 1: return items		Asmaller = [x for x in items if x < pivot]
2return quick_sort(smaller) + equal + quick_sort(larger)		Bequal = [x for x in items if x == pivot]
3Build the smaller list by keeping only the items less than the pivot		CThe equal list is missing, so the pivot and any duplicates of it are dropped from the result.
4Keep duplicates of the pivot in an equal list so they are not lost or sorted again		DThe recursive step: sort the smaller and larger lists, then join them around the equal items.
5if len(items) == 5: return items		EThe base case tests for the wrong length. It should be len(items) <= 1, otherwise short lists never stop and the recursion goes on until it crashes.
6return quick_sort(smaller) + quick_sort(larger)		FThe base case: a list with 0 or 1 items is already sorted, so it is returned and the recursion stops.

Definitions

return quick_sort(smaller) + equal + quick_sort(larger)

Fill in the Blanks

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

if len(items) __ 1: return items

smaller = [x for x in items if x _ pivot]

larger = [x for x in items if x _ pivot]

equal = [x for x in items if x __ pivot]

return (__________(smaller) + equal + quick_sort(larger))

Spot the Error

Shade in the letter of the line that contains an error.

Question 1

A def quick_sort(items):

B if len(items) >= 1:

C return items

D pivot = items[0]

E smaller = []

Question 2

A for x in items:

B if x < pivot:

C larger.append(x)

D else:

E larger.append(x)

Question 3

A def quick_sort(items):

B if len(items) <= 1:

C return items

D pivot = items[len(items)]

E larger = []

Question 4

A data = [5, 3, 5, 1, 3]

B result = quick_sort[data]

C print(result)

D # expect [1, 3, 3, 5, 5]

Question 5

A def quick_sort(items):

B if len(items) <= 1:

C return []

D pivot = items[0]

E smaller = []

F larger = []

Answer Key

Quick sort in Python

Section A: Quick Questions

B — if len(items) <= 1: return items

B — return quick_sort(smaller) + equal + quick_sort(larger)

A — [2, 1]

A — larger = [x for x in items if x > pivot]

A — So duplicates of the pivot are kept and not sorted again

Section B: Match the Pairs

if len(items) <= 1: return items → The base case: a list with 0 or 1 items is already sorted, so it is returned and the recursion stops.

return quick_sort(smaller) + equal + quick_sort(larger) → The recursive step: sort the smaller and larger lists, then join them around the equal items.

Build the smaller list by keeping only the items less than the pivot → smaller = [x for x in items if x < pivot]

Keep duplicates of the pivot in an equal list so they are not lost or sorted again → equal = [x for x in items if x == pivot]

if len(items) == 5: return items → The base case tests for the wrong length. It should be len(items) <= 1, otherwise short lists never stop and the recursion goes on until it crashes.

return quick_sort(smaller) + quick_sort(larger) → The equal list is missing, so the pivot and any duplicates of it are dropped from the result.

Section C: Definitions

return quick_sort(smaller) + equal + quick_sort(larger) — Recursive step of quick sort: sorts the smaller and larger lists by calling itself, then joins them around the equal items. Base case len(items) <= 1 stops it.

Section D: Fill in the Blanks

if len(items) <= 1:
    return items

smaller = [x for x in items if x < pivot]

larger = [x for x in items if x > pivot]

equal = [x for x in items if x == pivot]

return (quick_sort(smaller)
    + equal
    + quick_sort(larger))

Section E: Spot the Error

B — The base case must stop on lists of length 0 or 1, so it should be len(items) <= 1. With >= 1, every non-empty list is returned unsorted, and an empty list would crash at items[0].

C — Items smaller than the pivot belong in the smaller list, so this should be smaller.append(x). Putting them in larger leaves the smaller list empty and the sort is wrong.

D — The last valid index is len(items) - 1, so items[len(items)] causes an IndexError. Choose a valid pivot such as items[0].

B — A function is called with round brackets, not square brackets. It should be result = quick_sort(data).

C — The base case must return the list it was given (items). Returning [] throws away the single item, so values disappear from the sorted result.