Quick sort: pivot and partitioning

Name:

Date:

Class:

Quick Questions

Shade in the A or B circle for each question.

1. In quick sort, what is the pivot?

A A chosen item the other items are compared against

B The smallest item in the list, always

2. After partitioning around the pivot, where do the items go?

A Smaller items to one side, larger items to the other side

B All items stay in their original order

3. Quick sort is an example of divide and conquer. What does this mean?

A Compare every item with every other item one at a time

B Split the problem into smaller parts and solve each part the same way

4. List: [5, 2, 8, 1, 9]. If the first item is the pivot, which items go in the 'smaller' part?

A 8 and 9

B 2 and 1

5. When does quick sort stop splitting a part?

A When the part has 0 or 1 items

B When the pivot is the largest item

Match the Pairs

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

Left column		Right column
1pivot = items[0]		AThe pivot is missing from the result, so it is lost. It should be [pivot] between the two sorted parts.
2smaller = [x for x in items[1:] if x < pivot]		Bif len(items) <= 1: return items
3Divide and conquer: sort each part with the same method, then join the parts around the pivot		CThe pivot is still inside items, so the loop includes it. It can be duplicated or cause endless recursion. Use items[1:] so the pivot is left out.
4Base case: a list with 0 or 1 items is already sorted, so the recursion stops		DPartition step: collect the items that are smaller than the pivot into their own list
5smaller = [x for x in items if x < pivot] larger = [x for x in items if x > pivot]		EChoose the first item in the list as the pivot that the other items are compared against
6return quick_sort(smaller) + quick_sort(larger)		Freturn quick_sort(smaller) + [pivot] + quick_sort(larger)

Definitions

quick sort

Fill in the Blanks

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

pivot = items[_]

smaller = [x for x in rest if x < _____]

right = __________(larger)

if ___(items) <= 1:

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

Spot the Error

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

Question 1

A pivot = items

B smaller = []

C larger = []

D for x in items[1:]:

E if x < pivot:

F smaller.append(x)

Question 2

A def qs(a):

B if len(a) >= 1:

C return a

D p = a[0]

E lo, hi = split(a[1:], p)

F return qs(lo)+[p]+qs(hi)

Question 3

A define choose_pivot(a):

B mid = len(a) // 2

C return a[mid]

Question 4

A def partition(a, p):

B smaller = []

C larger = 0

D for x in a:

E if x < p:

F smaller.append(x)

Question 5

A pivot = items[0]

B smaller = larger = []

C for x in items[1:]:

D if x < pivot:

E smaller.append(x)

F else: larger.append(x)

Answer Key

Quick sort: pivot and partitioning

Section A: Quick Questions

A — A chosen item the other items are compared against

A — Smaller items to one side, larger items to the other side

B — Split the problem into smaller parts and solve each part the same way

B — 2 and 1

A — When the part has 0 or 1 items

Section B: Match the Pairs

pivot = items[0] → Choose the first item in the list as the pivot that the other items are compared against

smaller = [x for x in items[1:] if x < pivot] → Partition step: collect the items that are smaller than the pivot into their own list

Divide and conquer: sort each part with the same method, then join the parts around the pivot → return quick_sort(smaller) + [pivot] + quick_sort(larger)

Base case: a list with 0 or 1 items is already sorted, so the recursion stops → if len(items) <= 1: return items

smaller = [x for x in items if x < pivot] larger = [x for x in items if x > pivot] → The pivot is still inside items, so the loop includes it. It can be duplicated or cause endless recursion. Use items[1:] so the pivot is left out.

return quick_sort(smaller) + quick_sort(larger) → The pivot is missing from the result, so it is lost. It should be [pivot] between the two sorted parts.

Section C: Definitions

quick sort — Picks a pivot, splits the list into items smaller and larger than the pivot, then sorts each part the same way (recursion) until the parts are sorted.

Section D: Fill in the Blanks

pivot = items[0]

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

right = quick_sort(larger)

if len(items) <= 1:

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

Section E: Spot the Error

A — The pivot must be one item from the list, so it should be pivot = items[0]. Writing pivot = items makes the pivot the whole list, so it can't be compared with single items.

B — The base case must stop when the list has 0 or 1 items, so it should be if len(a) <= 1:. With >= almost every list returns early without being sorted, and an empty list never stops the recursion.

A — Python functions are started with the keyword def, not define. The line should be def choose_pivot(a):.

C — larger must start as an empty list so items can be added with .append(). It should be larger = []. A number has no append method.

B — This makes smaller and larger the same list, so items from both sides get mixed together. They need two separate lists: smaller, larger = [], [].