Week 10: Sorting
Quiz 4 on Friday. (Note, I’ll be out of town — for a conference this time.)
Lab 8 is available now. Please read the warning at the top of the page first.
Week 10 Topics
Continue analyzing / implementing binary search.
To explore the complexity of search, we will narrow the problem to searching for an item
x in a python list of items. Python already has two ways of doing this. The first is the Boolean
x in ls which returns
x is in the list
False otherwise. Python also supports the
index() method which will tell you the position in the list of the first occurrence of
x appears in the list. So
ls.index(x) will return an integer position if
x is in
x is not in the list, Python will generate an error called an exception that will likely crash your program since we have not talked much about how to handle exceptions in this class.
But how do these methods actually work? At some point, a computer scientist and python programmer designed and wrote the code for these built-in features. We will discuss the algorithm for searching a collection of items. Together, we’ll write a function
that does something familiar: search through a list for an item without using
in operator. Our functions will be called
To help illustrate the behavior of binary search, I’ve added a worksheet,
searchWorksheet.txt, to the
inclass/w09 directory. Before we finish our
implementations, let’s look at a couple of examples.
Implementing Binary Search
A key algorithmic question is: can we do better? In some cases, we can’t (and we can prove this!). In the case of linear search, we cannot do better in the general case. However, if all items in the collection are in sorted order, we can perform a faster algorithm known as binary search.
Binary search works using divide and conquer approach. Each step of the algorithm divides the number of items to search in half until it finds the value or has no items left to search. Here is some pseudocode for the algorithm:
set low = lowest-possible index set high = highest possible index LOOP: calculate middle index = (low + high) // 2 if item is at middle index, we're done (found it! return matching index) elif item is < middle item, set high to middle - 1 elif item is > middle item, set low to middle + 1 if low is ever greater than high, item not here (done, return -1)
Search Timing Comparison
I’ve implemented both linear search and binary search in a small program that
measures their performance (in terms of wall-clock time). I’ll share these
files with you (
timeBinarySearch.py), and we’ll run them
to see how long searching takes as we vary the size of the input list.
Sorted input is a prerequisite for binary search. While Python does have built-in support for sorting, let’s pretend it doesn’t in an attempt to better understand how sorting algorithms work.
Suppose you have an unsorted pile of exams, and you need to sort them alphabetically by name before you can enter them in a grading spreadsheet. For example, let’s say your exams are in this order:
Imagine these names are in a list, where
"Lisa" is at index 0,
"Andy" is at
index 1, etc.
Can you come up with an algorithm to sort them? Note: your algorithm can’t "just look at the name" to determine where an exam goes, it must systematically compare exams until every exam is in the right place.
What is the worst-case number of comparisons your algorithm would take?
When humans look at this problem, we may be able to look at multiple items at once and move large groups of items that are already in sorted order to the proper location. This concept is hard to express algorithmically however in a computer language, so instead we focus on a simpler operation that swaps only two elements at a time.
swap(lst, i, j) function will swap two items at positions
j in a list
lst. Once we have this small helper function working, we can use it to implement some sorting routines by comparing two elements at a time using Boolean relational operators, and calling
swap() if the elements are out of order. For example:
#assume i < j and we want to sort items in increasing order if lst[i] > lst[j]: #if items are out of order swap(ls, i, j)
In general, we will need to perform several swaps to sort an arbitrary list.
One approach to sort a list is to scan over the list and compare adjacent
elements — elements at index
i+1. If they are out of order, we will
swap. But one scan over this list may not be enough. So we can perform multiple
scans until the list is sorted. A list will be sorted when we perform zero swaps
while scanning the list.
keepGoing = True while keepGoing == True: #Optimistically assume we are done keepGoing = False for each adjacent pair of items: if out of order: swap keepGoing = True #another scan is needed