Computer Science · Grade 11

Active learning ideas

Quicksort and Advanced Sorting Techniques

Active learning fits this topic because Quicksort’s complexity is best understood through hands-on trial and error. Students must test pivot choices and see partitioning in action to truly grasp why performance varies. This approach turns abstract time-complexity into visible outcomes they can measure and discuss.

• Ontario Curriculum Expectations
• CS.HS.A.3
• CS.HS.A.4

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

Activity 01

• Collaborative Problem-Solving
• 45 min · Pairs

Pair Programming: Implement Basic Quicksort

Pairs write quicksort using first-element pivot, test on small arrays, then swap pivot to random and compare run times. Discuss observations before sharing with class. Extend to trace recursion on paper.

Evaluate the impact of pivot selection on Quicksort's performance.

Facilitation Tip

For Pair Programming: Implement Basic Quicksort, circulate to ensure both partners contribute to the code and understand each step of the partition function.

What to look for

Provide students with a small, unsorted array (e.g., [5, 2, 8, 1, 9]). Ask them to trace the first partitioning step of Quicksort using the first element as the pivot, showing the resulting array and the two sub-arrays.

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

Activity 02

• Collaborative Problem-Solving
• 50 min · Small Groups

Small Groups: Pivot Strategy Showdown

Groups receive datasets: random, sorted, reverse-sorted. Implement quicksort with three pivots (first, median, random), measure and graph times. Present findings on best pivot per distribution.

Compare Quicksort's average-case efficiency with its worst-case scenario.

Facilitation Tip

For Pivot Strategy Showdown, provide a dataset that students know is already sorted to demonstrate worst-case behavior with poor pivot choices.

What to look for

Pose the question: 'Imagine you are sorting an array of student scores from highest to lowest. Which pivot selection strategy might lead to the worst-case performance for Quicksort, and why? How could you mitigate this?'

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

Activity 03

• Collaborative Problem-Solving
• 30 min · Whole Class

Whole Class: Sorting Visualizer Challenge

Use an online visualizer tool. Class inputs arrays, watches quicksort vs. mergesort animations, votes on scenarios where one outperforms. Debrief on partitioning steps.

Design a strategy to optimize Quicksort for specific data distributions.

Facilitation Tip

For Sorting Visualizer Challenge, project the visualizer and pause after each partition to ask students to predict the next split before revealing it.

What to look for

Students pair up to review each other's Quicksort code implementation. They check for correct partitioning logic, proper recursive calls, and handling of base cases. Each reviewer provides one specific suggestion for improvement or identifies one potential bug.

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

Activity 04

• Collaborative Problem-Solving
• 40 min · Individual

Individual: Optimize for Real Data

Students fetch CSV data (e.g., student scores), implement optimized quicksort with median-of-three pivot, profile efficiency, and document improvements.

Evaluate the impact of pivot selection on Quicksort's performance.

What to look for

Provide students with a small, unsorted array (e.g., [5, 2, 8, 1, 9]). Ask them to trace the first partitioning step of Quicksort using the first element as the pivot, showing the resulting array and the two sub-arrays.

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

A few notes on teaching this unit

Teachers should start with concrete examples before abstract theory. Have students trace Quicksort on paper for tiny arrays, then move to code. Avoid rushing to recursion; emphasize base cases and stack depth through whiteboard traces. Research shows visualizing partitions helps students correct misconceptions about pivot balance and recursion depth.

By the end, students should confidently implement Quicksort, explain how pivot selection affects runtime, and compare it to other advanced sorts. They should articulate trade-offs between average and worst cases using evidence from their own coding and visualizations.

---

Watch Out for These Misconceptions

• During Pair Programming: Implement Basic Quicksort, some students may assume Quicksort is universally faster than other sorts.

  After the activity, ask pairs to time their implementation on random, sorted, and reverse-sorted arrays. Compare results with a provided mergesort implementation to show where Quicksort struggles and why pivot choice matters.

• During Pivot Strategy Showdown, students may think the middle element always guarantees balanced partitions.

  Ask groups to test median-of-three and random pivot strategies on the same dataset. Have them graph the depth of recursion for each strategy to reveal how unbalanced pivots lead to deep recursion.

• During Sorting Visualizer Challenge, students may believe recursion risks infinite loops without explicit base cases.

  Pause the visualizer at the base case (single element) and ask students to trace the call stack on the board. Have them identify how the algorithm stops and relate it to their code.

---

Methods used in this brief

• Collaborative Problem-Solving