Lesson plan

Sorting Robot Algorithm Race: Counting Comparisons

STEAM40 minutesGrades: 8th
Sorting Robot Algorithm Race: Counting Comparisons

Overview

Count a sorting robot's comparisons and graph the growth.

Description

Your teen acts as a sorting robot that can compare only two playing cards at a time. They count the comparisons needed to sort 2 to 8 cards using selection sort, graph the results, and discover that the work grows in a nonlinear way, unlike a simple 'find the biggest card' scan.

Objective

Your teen will run a sorting algorithm by hand, record comparisons for different input sizes, graph the data, and explain why one relationship is linear and the other is not.

Standards

8.F.3Math · Grade 8 · Functions
Interpret the equation y = mx + b as defining a linear function, whose graph is a straight line; give examples of functions that are not linear.
8.F.5Math · Grade 8 · Functions
Describe qualitatively the functional relationship between two quantities by analyzing a graph (e.g., where the function is increasing or decreasing, linear or nonlinear). Sketch a graph that exhibits the qualitative features of a function that has been described verbally.

Materials

ItemQuantity
Deck of playing cards (or numbered paper slips)1
Graph paper2 sheets
Pencil and tally sheet1 each
Two sticky notes labeled 'smallest so far' and 'sorted'2

Vocabulary

Algorithm
A step-by-step procedure for solving a problem.
Selection sort
A sorting algorithm that repeatedly finds the smallest remaining item and moves it to the sorted side.
Comparison
One check of which of two items is larger.
Nonlinear function
A relationship whose graph is not a straight line because it does not change at a constant rate.

Preparation

Introduction

Lay 8 cards face down. Say: 'A robot in a warehouse sorts packages, but it can only compare two at a time. How many comparisons will it need to put these in order?' Have your teen guess.
If 4 cards take a certain number of comparisons, will 8 cards take twice as many?
Why would a company care how many steps its robot takes?

Steps

1Step 1
Find the biggest
(6 min) Your teen flips 4 cards face up in a row and finds the largest by comparing two at a time, keeping the winner and tallying each comparison. Repeat for 2, 3, 6 and 8 cards and record the counts.
2Step 2
Run selection sort
(14 min) Your teen sorts 3, 4, 5, 6 and 8 cards with selection sort: compare to find the smallest card in the unsorted part, move it to the sorted side, and repeat. A partner tallies every comparison so the counts are exact.
3Step 3
Graph both
(8 min) Your teen plots both data sets on one graph with n on the x-axis and comparisons on the y-axis. They connect each set of points.
4Step 4
Analyze
(8 min) Your teen writes the equation for the find-the-biggest line (y = n - 1) and explains why it is linear. Then they describe the sorting graph in words, test the rule comparisons = n(n - 1) ÷ 2 against the data, and predict comparisons for 20 cards.

Conclusion

Ask: if a warehouse had 1,000 packages, why would programmers look for a faster sorting algorithm? Computer scientists study exactly this kind of growth to make software and robots efficient.

Make your own lesson plan in minutes

Describe a topic and Resource Portal AI writes the objectives, materials and steps for your group.

Try Resource Portal AI