Week 10: Sorting
Class Recordings
Announcements

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.

Sorting.
Monday
Linear 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 in
operator, x in ls
which returns True
if x
is in the list ls
and False
otherwise. Python also supports the index()
method which will tell you the position in the list of the first occurrence of x
, provided x
appears in the list. So ls.index(x)
will return an integer position if x
is in ls
. If 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 builtin 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
the in
operator. Our functions will be called contains
and position_of
.
Binary Search
Examples
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 = lowestpossible 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 wallclock time). I’ll share these
files with you (timeSearch.py
and timeBinarySearch.py
), and we’ll run them
to see how long searching takes as we vary the size of the input list.
Wednesday
Sorting
Sorted input is a prerequisite for binary search. While Python does have builtin 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:
Index  Name 

0 
Lisa 
1 
Andy 
2 
Tia 
3 
Rich 
4 
Vasanta 
5 
Ameet 
6 
Kevin 
7 
Lila 
8 
Joshua 
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 worstcase number of comparisons your algorithm would take?
Swap
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.
The swap(lst, i, j)
function will swap two items at positions i
and 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.
Bubble Sort
One approach to sort a list is to scan over the list and compare adjacent
elements — elements at index i
and 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