Teaching sorting algorithms with interactive videos

I am currently teaching a course on algorithms and data structures. One of the topics that I cover is sorting algorithms. I repeatedly tell my students about the importance of abstraction and how it helps us understand complex systems. This is a reason for us to use pseudo-code instead of an actual programming language: it helps us focus on the algorithm itself and not on the syntax of a particular language and its peculiarities.

More importantly, as more experienced computer scientists (I’m using this term very broadly - as anyone who understands and studies algorithms), we visualize the execution of algorithms in our minds. They are much more than just sequences of steps. In this higher abstraction level, we look at something like node = node->next and see a pointer moving from one node to the next in a linked list. We see data structures interacting with each other, and we see algorithms as processes that manipulate these structures. The execution of an algorithm becomes a little movie that we play in our minds.

The little movie in our minds

For some of us, it may be clear when we started to see algorithms this way. For other, like me, it’s not. I just know that at some point I started to see it. Of course, I had great teachers that helped me develop this skill. As I try to trace back my steps, I realize that the little sketches that they made on the board were crucial. As they explained the algorithms, they pointed to the static sketches and moved their fingers around them, showing how the algorithm worked. They would erase and draw again, showing how the algorithm changed the data structures. They would repeat the process, showing how the algorithm worked on different inputs.

That was much more effective than what I gave them credit for at the time I was a student. My algorithms teachers were among the best teachers I had.

When I was picking up a topic for my PhD, I was divided between algorithms and Human-Computer Interaction (HCI). I ended up choosing HCI, and I don’t regret it. I love HCI. But I also love algorithms. And I love teaching them. As I was offered the opportunity to teach algorithms and data structures, I was thrilled. It was a great chance to use my knowledge of HCI to teach algorithms.

Transferring mental models

One of the things that I wanted to do was to create interactive simulations of algorithms. I wanted to create something that would help my students visualize the movie that plays in my mind. This is what we call the mental model in HCI.

The point of this post is not to discuss mental models, but I wanted to mention them because that’s what I wanted to do: to help my students build a mental model of sorting algorithms. In other words, I wanted to help them learn how to visualize the execution of sorting algorithms in their minds.

Tools

I’ve developed my teaching materials using React , Remotion and Astro.build . The theory is mostly taken from the book Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein (CLRS) and Jeff Erickson’s “Algorithms” . Again, though I love theory and algorithms, it is not my field of expertise, so I thought it would be best to leave the explanations to the experts. I copied the pseudo-code from CLRS and wanted to make it look familiar to the students, so I also copied their style. What I did was essentially to create a visual representation of the pseudo-code.

For each algorithm, I created a TypeScript implementation that outputs an array of events. Each event is basically a snapshot of the state of the algorithm and the memory at a given time. I then created a React component that plays these events as a video.

In the following sections I’ll show you some of the materials I’ve developed. The goal is just to share the idea. The actual code is not available as a standalone project, but I can share it with you if you’re interested.

Videos

Insertion Sort

The first video I created was for the Insertion Sort algorithm. This is a simple algorithm that is easy to understand and visualize. The video is below. What I wanted to show here is that the variables i and j should be understood as pointers to elements of the array.

Students can use the parameters to control the speed of the video and to test the algorithm with different inputs. During the class I ask them to look for best and worst-case scenarios. After experimenting with the algorithm, I ask them to come up with a formula to count the exact number of executions of each line of the algorithm.

Selection Sort

Nothing really new here. The video below shows the Selection Sort algorithm. It’s just another example for the students to practice visualizing the execution of an algorithm.

Bubblesort

Just another example.

But for this one, after discussing a possible optimization, they can access the second version of the video.

Counting Sort

Students who finish the previous exercises quickly get to work with more challenging ones: Counting Sort and Radix Sort. After discussing the lower bound for sorting algorithms based on comparisons, I introduce Counting Sort.

Here, the auxiliary arrays that store the counts that are used later as indices are a bit confusing. I still have to think carefully when I’m visualizing the algorithm. I think there’s a lot of room for improvement in this video. But it’s a start.

Radix Sort

The last sorting algorithm that I cover is Radix Sort. This depends on Counting Sort, so students have to finish the previous exercise before moving on to this one.

Conclusion

I hope you enjoyed the videos. I’m still working on the materials, and I’m planning to create more videos for other algorithms. The feedbacks so far have been positive. I’m happy to see that the students are enjoying the materials. I’m even happier that they seem to actually be learning something. I still don’t have any data to back this up (and, honestly, I’m not sure I’ll do it), but I’m happy with the results so far.