analysis.py, summary.txt - empirically testing sorting algorithms

We've seen several sorting algorithms, namely: insertion sort, selection sort, quicksort, merge sort, and bubble sort. In practice, people use hybrid sorting algorithms for serious implementations.Links to an external site. For example, a popular choice (called TimsortLinks to an external site.) is to use merge sort that switches to insertion sort for small lists (63 or fewer items, typically). Actually implementing sort algorithms is fairly advanced work: you need to carefully measure performance on a variety of inputs while running on a variety of hardware systems.

Let's do some measurement of our own, on a simpler scale. Take the sorting algorithms we've seen so far and copy them into the workspace. (If you couldn't complete bubble sort, just leave it out.)

Your job is to come up with a variety of input lists for these sorts and to compute some statistics about them. In particular, we'd like to know for each input on each sort (a) how many comparisons are done, and (b) how many swaps are done (if applicable). To get these numbers, the easiest thing to do is to instrument the sorting algorithms themselves to use special compare and swap functions that count how many times they're called; you can reset them between runs.

You should produce a file summary.txt that contains: A description of five different input lists that you'll do the comparison on. We recommend generating these lists with functions that you write. Since these lists may be too large to write down for human eyes---just explain them in the summary.

The data for each sorting algorithm on each list: how many comparisons and swaps (if applicable) does it do?

A brief explanation of why these lists are a good benchmark. (In what way are they diverse/representative of different workloads?)

You should also include a file analysis.py that contains all of the code you used to do your analysis. We expect to be able to run this code and see how it relates to your summary.txt.