← VCE Software Development U3O1

Quick sort: pivot and partitioning

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.

Part of: VCE Software Development - U3O1 - Programming — Module 152

Understanding Quick sort: pivot and partitioning in VCE Software Development U3O1

What it does: The function calls itself on the smaller and larger parts, then joins them with the pivot in the middle. Without this base case the function would keep calling itself forever. A short list needs no sorting. The pivot can be any item (first, last, middle or random). Every other item is compared to it to decide which part it goes in. Divide and conquer breaks a big list into smaller lists, then sorts each smaller list using the same method (recursion). The pivot is 5. Items less than 5 are 2 and 1. Items greater than 5 are 8 and 9.

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

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 Quick sort: pivot and partitioning to a class →

This module's key terms are also in a printable crossword (Modules 142–155) 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
In quick sort, what is the pivot?
A chosen item the other items are compared againstThe smallest item in the list, always
Matches
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.
Applying
Meanings
Term
quick sort
Meaning
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.
Practice
def quick_sort(items):
Testing
Gaps
pivot = items[]
Check Answer
Spots
1pivot = items
2smaller = []

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

The 'Constellation Wolf' badge — Space Legend, 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. 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
The pivot can be any item (first, last, middle or random). Every other item is compared to it to decide which part it goes in.
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
Partitioning splits the list into items smaller than the pivot and items larger than the pivot (equal items go to one chosen side).
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 ✓
Divide and conquer breaks a big list into smaller lists, then sorts each smaller list using the same method (recursion).
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 ✓
The pivot is 5. Items less than 5 are 2 and 1. Items greater than 5 are 8 and 9.
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
A part with 0 or 1 items is already sorted. This is the base case that stops the recursion.

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.

Key Term

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.

Fill in the Blanks

1. pivot = items[0]
Hint: Type the index of the first item in the list, which is chosen as the pivot.
2. smaller = [x for x in rest if x < pivot]
Hint: Type the variable that every item is compared against when partitioning.
3. right = quick_sort(larger)
Hint: Type the name of the function that sorts the larger part the same way (recursion).
4. if len(items) <= 1:
Hint: Type the built-in function that counts how many items are in the list, used to check the base case.
5. larger = [x for x in rest if x >= pivot]
Hint: Type the variable holding every item except the pivot, which is split into the larger part.

Spot the Error

Question 1
A pivot = items
B smaller = []
C larger = []
D for x in items[1:]:
E if x < pivot:
F smaller.append(x)
Line 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.
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)
Line 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.
Question 3
A define choose_pivot(a):
B mid = len(a) // 2
C return a[mid]
Line A — Python functions are started with the keyword def, not define. The line should be def choose_pivot(a):.
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)
Line 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.
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)
Line B — This makes smaller and larger the same list, so items from both sides get mixed together. They need two separate lists: smaller, larger = [], [].

Student with a class code? Join your class →