Warning: Outdated Content
This lab is from a previous version of CS 125. Click here to access the latest version.
Sorting and Searching
Sorting and searching are fundamental computer science tasks. They get to the heart of two things that computers are very good at: organizing and retrieving data. They are also building blocks on which other algorithms are built.
Today’s lab introduces you to basic searching and sorting algorithms. You’ll have the chance to implement two classic algorithms: Bubblesort and binary search.
1. Bubblesort (30 Minutes)
At this point we’ve discussed multiple sorting algorithms in class, and you’re getting practice at implementing them on our homework problems this week. We’ve talked about iterative approaches (insertion sort) and recursive approaches (Mergesort and Quicksort).
But we can’t finish up sorting without discussing a classic sorting algorithm: Bubblesort. The idea behind Bubblesort is simple: scan the array, and if you find any two adjacent items that are out of order, swap them. Repeat this process until you find no elements to swap, at which point the array is sorted. Here’s a great visualization of how the algorithm works.
OK—get on to today’s lab homework to complete Bubblesort as a warm up to the next programming part of the lab.
2. Binary Search (60 Minutes)
We discussed in class how we could structure binary trees to make searching more efficient. It turns out that we can also structure our array to make searching more efficient—by sorting them, which we now know how to do!
How does this work? Let’s use the famous phone book analogy, since it also contains sorted information. Imagine you are looking for someone in the phone book. You could start at the beginning and flip through every page, one by one— a linear search that would take forever.
But you’re smarter than that. You open the book at around the midway point. That allows you to determine whether the name you are looking for is before or after the entries on that page, meaning that you’ve reduced the number of items you need to search for by half. Nice! (This is the origin of the famous CS 50 phone book sorting video.)
There are multiple ways to implement a binary search on an array, and we’re going to let you wrestle with this a bit on today’s lab homework. However, here are some hints:
-
You can but don’t have to implement the algorithm recursively—our solution uses an iterative approach.
-
You probably need to track the start and end indices of the part of the array you are still searching. Then, in each step, you either update the start or the end, depending on whether you need to search the front or back half of the unsearched portion.
-
Off-by-one errors are common here—be careful! Feel free to work with a partner and sketch out approaches on a white board.
2.1. Picking a Project Partner (20 Minutes)
The final project description will be released in less than one week, so even though you are wrapping up MP4 we want you to think ahead to your final project.
Today you should pick someone that you will work with on your final project and in lab together for the next few weeks. Obviously you want to find someone to work with that you enjoy working with and think that you can do an awesome project with—since we will be giving extra credit for some of the best projects. Another consideration is ensuring that at least one of you has a laptop that can smoothly run Android Studio and the emulator, or an Android phone for demoing your new application.
If you would like to work with someone from another lab section, you must both attend the same lab and work together for the remaining three labs. This means that only one of you will receive participation credit for that lab. You will not receive credit for working in lab without your partner. If you want to work with someone from another lab, this is the tradeoff you will have to make. (Remember that you have three excused lab absences.)
4. Before You Leave
Don’t leave lab until:
-
You’ve completed our in-lab homework problems.
-
You’ve finished MP4…
-
And so has everyone else in your lab!
If you need more help completing the tasks above please come to office hours or post on the {forum}.