How to teach sorting algorithms

Why this matters

A student who can write bubble sort in five lines can believe it beats a longer selection sort, because shorter code looks faster. Counting the comparisons and swaps on one real list shows the opposite, and a list that is already in order flips the answer back. An answer key can mark the claim wrong but can't point the student to the numbers they counted, and the teacher has to wait for the unit test to find out who still judges speed by line count.

Two sorting algorithms: selection sort and bubble sort

A sorting algorithm is a set of steps that puts a list in order. Students compare two sorting algorithms by counting their work: a comparison checks which of two items comes first, and a swap trades two items' places.

• Selection sort finds the smallest item in the unsorted part of the list and swaps it into the next spot. On a list of n items it always makes n(n−1)/2 comparisons, 15 for 6 items, however the list starts, and at most n−1 swaps (Wikipedia: Selection sort).
• Bubble sort steps through the list, compares each pair of neighbors and swaps them when they are out of order, pass after pass, until a pass makes no swaps. On a list that is already sorted, the version that stops early finishes after one pass (Wikipedia: Bubble sort).

On the activity's shuffled 6-song playlist, selection sort makes 15 comparisons and 4 swaps, and bubble sort makes 20 comparisons and 8 swaps. On the same songs already in order, bubble sort makes 5 comparisons and selection sort still makes 15.

In the Flint activity, each student sorts a 6-song playlist both ways in a playlist sorter that counts comparisons and swaps, then codes the faster algorithm in Python or Java. When a student's claim doesn't match their counts, Sparky sends them back to those counts, which a worksheet can't do.

Sparky gets Jalen to judge speed by his own counts

Jalen ends up judging an algorithm's speed by the work it does and explaining why bubble sort wins on a sorted list. Every student gets the same activity, and Sparky's replies depend on the counts and claims each student sends.

Sparky sends Jalen back to his own countsA right answer gets a harder question

J

Jalen

Interest: Making playlistsStarting point: Thinks shorter code sorts faster

Sparky

In the playlist sorter, put the 6 songs in order from shortest to longest, once with each algorithm. When you finish both, tell me how many comparisons and swaps each one took, and which algorithm you think is faster.

Jalen

bubble sort took 20 comparisons and 8 swaps. i think bubble sort is faster tho, the code for it is way shorter

Sparky

An algorithm's speed is about how much work it does, and you already measured that. Look back at your comparison and swap counts: which algorithm did less total work on that playlist?

Jalen

15 comparisons vs 20, and only 4 swaps vs 8. so selection is faster even tho the code is longer

Understanding check

Now here's a harder one: go back to the Playlist Sorter and hit "Start already sorted", so the songs are already in order. What do the comparison and swap counts look like now, and does the same algorithm "win"?

Jalen

with it already sorted, bubble did 5 comparisons and 0 swaps. selection still did 15 comparisons and 0 swaps

Sparky

Neither algorithm is always faster. So what's different about bubble sort that lets it do only 5 comparisons on a sorted list, while selection sort still grinds through all 15?

Jalen

bubble went through once and nothing needed a swap so it just stopped. selection doesnt know its sorted, it still checks every song left to find the shortest one each time

Judged speed by his counts, not code length, and explained early stopping

Jalen is an example student, and Sparky's replies are shortened.

What Flint did for Jalen

• Sparky's playlist sorter counted Jalen's comparisons and swaps while he sorted the songs both ways.
• When Jalen called bubble sort faster because its code was shorter, Sparky sent him back to his own counts.
• Once his claim matched his counts, Sparky asked about an already-sorted playlist, where bubble sort wins.

A teacher can't do this by hand for 30 students, and Sparky does it in every student's chat.

The activity page shows who still picks the shorter code

While the class works, Needs attention shows the teacher which student is stuck and on which message. After three or more students submit, activity analytics lists what the class explained well, where students went wrong, and a follow-up to practice next.

Set up the activity for free

The playlist activity is in Flint's public library, with the playlist sorter, Sparky's guidelines and the greeting already written. Select Use activity to copy it into a free Flint account and assign it to a class. In Java, Flint's code editor doesn't run main() by itself, so students call their sort method on the last line of their code, outside the class.

For a lesson that introduces a new concept, see how to use AI to teach computer science. For more computer science activities, see Flint for computer science.