Sorting Algorithms: Bubble and Insertion Sort

Active learning helps students grasp sorting algorithms because tracing passes and physical card movements make abstract comparisons and shifts visible. When students implement bubble and insertion sort themselves, they see how small changes in data order affect performance, which builds deeper understanding than reading or listening alone.

• Year 11
• Computing
• 4 activities
• 20 min–40 min

Learning Objectives

1. Compare the number of comparisons and swaps made by Bubble Sort on a nearly sorted list versus a reverse-sorted list.
2. Differentiate between the best-case and worst-case scenarios for Insertion Sort, explaining the input conditions for each.
3. Construct a trace table to accurately demonstrate the step-by-step execution of Bubble Sort on a given dataset.
4. Analyze the time complexity of Bubble Sort and Insertion Sort by evaluating their performance on different input sizes.
5. Implement both Bubble Sort and Insertion Sort algorithms in a programming language.

Problem-Based Learning

⏱ 30 min·Pairs

Pair Programming: Bubble Sort Implementation

Pairs write bubble sort in pseudocode or Python, test on lists of 5-10 numbers, and log swaps per pass. Switch roles midway. Compare results against a sorted list to spot early termination.

Prepare & details

Analyze the number of comparisons and swaps required by Bubble Sort for a nearly sorted list.

Facilitation Tip: During Pair Programming: Bubble Sort Implementation, circulate and ask pairs to verbalize their swap decisions step-by-step to catch off-by-one errors early.

Setup: Groups at tables with access to research materials

Materials: Problem scenario document, KWL chart or inquiry framework, Resource library, Solution presentation template

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

Problem-Based Learning

⏱ 40 min·Small Groups

Small Groups: Insertion Sort Card Challenge

Groups receive shuffled cards numbered 1-20. Perform insertion sort by building sorted pile, timing the process. Rotate roles: inserter, timer, observer. Graph times for random versus nearly sorted decks.

Prepare & details

Differentiate between the best-case and worst-case scenarios for Insertion Sort.

Facilitation Tip: In Small Groups: Insertion Sort Card Challenge, provide decks with color-coded ends so students quickly spot nearly sorted sections to reinforce best-case scenarios.

Setup: Groups at tables with access to research materials

Materials: Problem scenario document, KWL chart or inquiry framework, Resource library, Solution presentation template

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

Problem-Based Learning

⏱ 25 min·Whole Class

Whole Class: Trace Table Relay

Project a dataset; class divides into teams. One student per team fills one row of the trace table on whiteboard, passes marker. First accurate table wins. Debrief on common errors.

Prepare & details

Construct a trace table to demonstrate the execution of Bubble Sort on a given dataset.

Facilitation Tip: In Whole Class: Trace Table Relay, assign roles like ‘comparer’ and ‘recorder’ to ensure every student contributes to the shared table.

Setup: Groups at tables with access to research materials

Materials: Problem scenario document, KWL chart or inquiry framework, Resource library, Solution presentation template

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

Problem-Based Learning

⏱ 20 min·Individual

Individual: Efficiency Comparison Sheets

Students trace bubble and insertion on three datasets (sorted, random, reverse). Tally operations in tables. Plot bars to visualize differences. Share one insight with neighbor.

Prepare & details

Analyze the number of comparisons and swaps required by Bubble Sort for a nearly sorted list.

Setup: Groups at tables with access to research materials

Materials: Problem scenario document, KWL chart or inquiry framework, Resource library, Solution presentation template

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

Teaching This Topic

Teach sorting algorithms by alternating concrete card work with abstract tracing to bridge the gap between action and notation. Avoid rushing to code—let students feel the ‘shift’ in insertion sort and the ‘bubble’ in bubble sort first. Research shows that students who physically manipulate data before tracing retain concepts longer and make fewer off-by-one errors.

What to Expect

Students will confidently trace bubble and insertion sort on small datasets, counting comparisons and swaps accurately. They will explain when each algorithm performs best and why, using concrete examples from their trace tables and card sorting activities.

Watch Out for These Misconceptions

Common Misconception

During Pair Programming: Bubble Sort Implementation, watch for students assuming bubble sort always needs the maximum number of passes.

What to Teach Instead

Use the pre-written early-termination condition in the starter code to show how the algorithm checks for swaps and stops early on nearly sorted data, then have pairs modify their loop to test this behavior.

Common Misconception

During Small Groups: Insertion Sort Card Challenge, watch for students performing adjacent swaps instead of shifting elements to make space.

What to Teach Instead

Have students physically slide cards rightward to create space for the new element, then write the corresponding array state after each shift to connect the action to the algorithm.

Common Misconception

During Whole Class: Trace Table Relay, watch for students believing insertion sort requires as many operations in the best case as in the worst case.

What to Teach Instead

Assign one team the sorted dataset and have them race through the relay, highlighting that only n-1 comparisons occur, then contrast this with a reverse-sorted team’s full trace to make the difference visible.

Assessment Ideas

Quick Check

After Pair Programming: Bubble Sort Implementation, give students a new small list and ask them to predict the number of swaps and comparisons before running the algorithm, then compare their predictions to the actual counts.

Exit Ticket

During Small Groups: Insertion Sort Card Challenge, collect each group’s final sorted deck and trace table, then ask students to write one sentence explaining why insertion sort performs fewer operations on nearly sorted data.

Discussion Prompt

After Whole Class: Trace Table Relay, pose the scenario of sorting 1000 already-sorted items and ask students to justify their choice of algorithm based on the relay’s evidence, calling on multiple volunteers to share their reasoning.

Extensions & Scaffolding

• Challenge: Ask students to invent a hybrid sort that combines the best of bubble and insertion sorts for nearly sorted data, then trace its performance on a new dataset.
• Scaffolding: For students struggling with insertion sort, provide a partially filled trace table with the first two elements already sorted to focus on the shifting process.
• Deeper exploration: Have students research why insertion sort is preferred for small datasets despite O(n^2) complexity, citing real-world applications like sorting a hand of cards.

Key Vocabulary

Bubble Sort	A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.
Insertion Sort	A simple sorting algorithm that builds the final sorted array one item at a time. It iterates through the input list and for each element, it finds the correct position within the already sorted portion of the list and inserts it there.
Comparison	An operation where two elements are checked to determine their relative order, crucial for deciding if a swap is needed in sorting algorithms.
Swap	An operation where the positions of two elements in a list are exchanged, typically performed when elements are found to be out of order.
Trace Table	A table used to track the state of variables and the execution flow of an algorithm step by step, useful for debugging and understanding algorithm behavior.