Sorting and Searching

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.

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:

Don’t leave lab until: