My algorithms class is studying sorts this week. I felt like we needed a little hands on sorting to get an understanding of how some sorts related to the types of sorting people do. I had a number of decks of playing cards and their easy yo hand out and to sort. I don’t have one deck for each student and watching others sort is boring. You really want to avoid boring this close to the end of the year so I decided that I could split the decks by suit and have enough small decks for each student. Faster is often better anyway.
My students had been assigned some reading on Insertion, selection, and bubble sorts. I was interested to see if they would relate any of these to their chosen sort methods. Not bubble sort though. I wonder if we should even teach that one. But I digress.
The students were asked to sort their deck which they all did pretty quickly. Than I asked them if they used a selection sort or an insertion sort. About half of the students choose each one. This led to a good discussion of the two methods. It made for a good exercise introduction.
As a side issue, I had my beginner class separate the decks into suits. This was part of a discussion about While loops and the need to properly plan for data storage (the four output files), That it meant I didn’t have to do the separation was a nice side benefit.
In both classes, we had a brief talk about parallel processing and breaking a problem up into parts that could be run in parallels by separate processors. I take my lessons where I find them.
Back when parallel processing was a new thing, I would use the bubble sort algorithm to demonstrate how it worked. If I remember correctly, students were in a line (i.e., an array), each holding a card. Students in the odd numbered positions in the line were the CPUs. Each CPU compared his/her value to the value of the adjacent student, and on a signal all pairs who should swap positions did so. Repeat until no swaps are required.
ReplyDeleteHaving students hold one card each and move (as opposed to just moving cards on a table) is a good way to introduce efficiency and Big-O.
Using a partial decks that includes more than one suit is a good way to introduce the idea of primary and secondary sort keys. If the initial instructions to "sort the cards" are deliberately vague, either someone will ask about sorting by suit or rank, or some students will sort the deck each way.
I occasional get out of sorts but that is about it.
ReplyDelete