Week 10: Sorting
Announcements

Quiz 4 on Friday.

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.
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.
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(ls, i, j)
function will swap two items at positions i
and j
in a list ls
. 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, e.g.,
#assume i<j and we want to sort
#in increasing order
if ls[i] > ls[j]: #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 scan 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