Description
learning goals
In this lab you will measure the performance of algorithms for sorting lists.
set-up
Download sort.py, test sort.py, and chart.xls, saving them to a sub-directory called lab8. Notice that test sort.py uses module timeit to measure total time used, and cProle to nd out which parts of your
code are costing the most time.
Note: If you’re using Wing, there is an (in)compatibility issue that means you must run the tests in debug mode.
big-Oh characteristics of sorting algorithms
In this section you will test various sorting algorithms to see, empirically, which complexity class they fall into. The key idea is to notice how quickly the running time grows as you increase the size of the problem | the number of elements in a list in this case.
Open test sort.py in your IDE, and press the run button. Various results should print in the console. Warning: We have tried to choose the size of the lists being sorted so that the experiment takes a
reasonable amount of time. You are welcome to change these parameters, but notice that the running times may increase to take longer than you are comfortable with.
As you work through the various sorting algorithms, record your results on chart.xls. To graph your results, select all the rows for, say, the randomized sort. Then choose the chart tool from the toolbar, use
the wizard to select points and lines as the chart type, and under Data Range select Data Series in rows, and
2
