with Leigh Ann Yoder
Searching and Sorting!
Today we quickly recapped our Searching Algorithm lesson from last week which demonstrated Linear Searching. Next, we played two more Battleship games illustrating new algorithms. The first was a Binary Search, similar to one of the fairy tales read for homework. The students easily identified that this method is always better than a linear search, but requires the data to be sorted first. The last Battleship game illustrated Hashing. Quickly, students discovered hashing can be much more efficient than a binary search, yet they also recognized that there could be instances when hashing is no better than a linear search. We briefly discussed Hash Tags (#), and everyone should now have a basic understanding.
Using the example of a grocery store check out, we discussed the various searching algorithms. It became clear to the students why an efficient search is necessary. No one wants to stand at the checkout line waiting 10 seconds for each item to scan. It is not necessary for students to memorize these different algorithms. I want them to have familiarity and to understand that computer scientists have a variety of algorithms to choose from, and often they will use a combination of algorithms based on the application.
After identifying that searching methods are much more efficient if the data is first sorted in some order, we moved on to our next topic: Sorting Algorithms. First, we discussed the many applications that require organized data and how we use it every day. Students gave examples such as their music being organized, emails, documents, and phone numbers.
We used eight film canisters filled with different amounts of salt and a simple balance to sort the canisters from lightest to heaviest to explore sorting algorithms. The students worked in pairs, acting as the computer. Working in an organized manner, we used the Selection Sort Algorithm and the Quicksort Algorithm. Of course, they easily identified the Quicksort as more efficient.
Using human volunteers, we also did class demonstrations of Insertion Sort and Bubble Sort. I explained to the class that there are other sorting algorithms available to computer scientists, and often combinations can be used for different data sets. Again, memorization is not expected, just familiarity.