Computer Science · Grade 12

Active learning ideas

Sorting Algorithms: Advanced (QuickSort)

Active learning works well for QuickSort because its abstract steps become visible when students manipulate physical cards and debug code. Tracing pivots and partitions by hand builds intuition for why balanced splits matter, while coding shows how algorithms translate to behavior.

• Ontario Curriculum Expectations
• CS.AA.9
• CS.P.19

• 25–50 min
• Pairs → Whole Class
• 4 activities

Activity 01

• Collaborative Problem-Solving
• 35 min · Pairs

Pairs Activity: Manual Card QuickSort

Give pairs 20-30 shuffled index cards numbered 1-50. They pick a pivot, partition by hand into left/right piles, recurse on piles until sorted. Pairs sketch recursion trees and note partition balance. Share findings with the class.

How does the choice of a pivot element impact the efficiency of QuickSort?

Facilitation Tip

During the Pairs Activity: Manual Card QuickSort, circulate to ensure students mark pivots clearly and swap cards without lifting them, reinforcing the in-place partitioning concept.

What to look for

Provide students with a small, unsorted array and a chosen pivot element. Ask them to trace the partitioning process step-by-step, showing the state of the array after each swap, and to identify the final position of the pivot.

• Apply
• Analyze
• Evaluate
• Create
• Relationship Skills
• Decision-Making
• Self-Management

Activity 02

• Collaborative Problem-Solving
• 50 min · Small Groups

Small Groups: Pivot Variant Coding

Groups code QuickSort in Python with three pivot choices: first, random, median-of-three. Test on 10,000-element arrays of random, sorted, reverse-sorted data. Time runs, graph results, discuss patterns.

Explain the partitioning process in QuickSort and its role in sorting.

Facilitation Tip

In Small Groups: Pivot Variant Coding, ask groups to explain their pivot selection to you before running tests, so they articulate why median-of-three often outperforms first/last element.

What to look for

Pose the question: 'If you are given an array that is already sorted in ascending order, what pivot selection strategy would lead to the worst-case performance for QuickSort, and why? Propose an alternative strategy to mitigate this issue.'

• Apply
• Analyze
• Evaluate
• Create
• Relationship Skills
• Decision-Making
• Self-Management

Activity 03

• Collaborative Problem-Solving
• 25 min · Whole Class

Whole Class: Worst-Case Walkthrough

Display a sorted array on the board or screen. Class selects pivots step-by-step, simulates partitions aloud, counts comparisons. Switch to randomized pivot to contrast depths and efficiency.

Critique the worst-case performance of QuickSort and suggest mitigation strategies.

Facilitation Tip

During Whole Class: Worst-Case Walkthrough, deliberately provoke imbalance by feeding a sorted array and time the walkthrough to show O(n^2) behavior on the board.

What to look for

Present students with pseudocode for QuickSort and ask them to identify where the pivot selection occurs and where the partitioning logic is implemented. They should also write the recurrence relation for the average-case time complexity.

• Apply
• Analyze
• Evaluate
• Create
• Relationship Skills
• Decision-Making
• Self-Management

Activity 04

• Collaborative Problem-Solving
• 30 min · Individual

Individual: Trace and Analyze

Provide printed arrays for students to trace QuickSort manually with given pivots. Compute recursion depths, estimate comparisons. Submit sheets with efficiency critiques.

How does the choice of a pivot element impact the efficiency of QuickSort?

What to look for

Provide students with a small, unsorted array and a chosen pivot element. Ask them to trace the partitioning process step-by-step, showing the state of the array after each swap, and to identify the final position of the pivot.

• Apply
• Analyze
• Evaluate
• Create
• Relationship Skills
• Decision-Making
• Self-Management

A few notes on teaching this unit

Teachers should begin with physical sorting to ground the algorithm, then move to code so students see how abstract steps map to instructions. Avoid starting with the pseudocode or recurrence relations, as students need to feel the pain of imbalance before they care about the math. Research shows tracing with color-coding or step markers reduces cognitive load during recursion.

By the end, students should explain how pivot choice affects performance, trace partitioning steps without confusion, and debug recursive calls to correct imbalance. They should connect O(n log n) average case and O(n^2) worst case to concrete examples they have created and measured.

---

Watch Out for These Misconceptions

• During Pairs Activity: Manual Card QuickSort, watch for students assuming every run will finish in O(n log n) time. Redirect by timing their card swaps on a nearly sorted pile and asking them to recount partitions.

  Prompt them to select the first card as pivot for a sorted array, trace the partitions, and count the steps to show O(n^2) clearly on their desk.

• During Small Groups: Pivot Variant Coding, listen for comments that partitioning requires extra arrays. Redirect by asking groups to point at their swap operations and explain how the same array is reused.

  Have them annotate their code with comments showing where swaps occur and why no new array is allocated.

• During Whole Class: Worst-Case Walkthrough, some students may believe random pivots always prevent imbalance. Redirect by running the walkthrough on a small array where random pivots still create uneven splits.

  Ask the class to articulate why randomness avoids worst case only probabilistically, and have them sketch the recurrence tree for that specific run.

---

Methods used in this brief

• Collaborative Problem-Solving