Class Notes Week 10

Week 10 Topics

Monday Wednesday Friday

• Finish Search Analysis
• Sorting Algorithms
• Selection Sort, Bubble Sort
• Complexity of Sorting

Search Analysis

Last week you saw two algorithms for searching through lists: linear search and binary search. This week, we'll start by empirically analyzing the runtime of each algorithm, using the python time library.

from time import time

The time() function measures the time in seconds since the last "epoch". We'd like to use this function to measure how long our code takes to run. To do so, call time() both before and after the code you're measuring, and take the difference.

start = time()
# now do what you want to time
...
end = time()

Exercise: timing search algorithms

Open the program timeSearch.py. This program will test the running time of two search implementations: mysterySearchA and mysterySearchB. One uses lienar search; the other binary search. Test the runtime of each function to determine which is which. Also see how the runtime scales with the length of the list. Do the changes in runtime match our intuition?

Sorting Algorithms

A second core problem computers are asked to solve is the sorting problem. Broadly speaking, the sorting problem takes a list of items and sorts them. The items can be numbers, words, or any other type that is comparable.

• Facilitate fast searching by ordering items so we can use binary search.
• Sort Languages by number of speakers
• Amazon, sort Hippo Children's books by price!

def sort(L):
  """
  Parameters: L, a list
  Returns: none, but L is becomes sorted
  """

For today, assume the list is numbers, and you have the following operations:

• compare(a,b): return True iff a<b
• swap(a,b): swap values of items a,b

Exercise

Using playing cards, work with a neighbor and try to come up with a specific algorithm to sort a list of items. Write your algorithm in pseudocode, and test it by running several examples using the playing cards.