Week 10: Sorting

Class Recordings

To access recordings, sign in to YouTube with your @swarthmore.edu account.

Monday Wednesday Friday (No recording)

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 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 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 = 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 (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 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(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