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 wall-clock 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 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:

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 worst-case 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