CSC148 - Lab 8
Comparisons and Swaps
In lecture, we briefly went over the runtimes of all the sorting algorithms we have studied so far. We would now like to analyze them analytically.
We will be interested in calculating two values for each sorting algorithm, given an input list A; how many comparies between elements of A the algorithm performs, and how many times elements of A are swapped.
To start, download sorts.py which contains
implementations of bubble sort, selection sort, and merge sort (note
that merge sort does not perform swaps; in this case, count how many
times the merge routine moves objects into list_c).
Modify each of these methods to return a tuple (comps, swaps), the number of comparisons and swaps performed.
Consider the following questions:
1) In the worst case, how many swaps/comparisons would you expect bubble/selection/merge sort to do? (approximately)
2) In the best case, how many swaps/comparisons would each do?
3) What is the minimum number of swaps any sorting algorithm would have to perform? Do any you think any of these three algorithms achieves this?
Finally, use your modified code to run an experiment. For each of the algorithms, pick a couple of values of n (the length of the list we are sorting) and see how many swaps/comparisons the algorithm performs on lists of length n. Use random.shuffle to generate some number (maybe 10-15) random lists to sort, and take the average number of swaps/comparisons done for each of those lists. Compare these numbers to n and your estimates from answering the above questions.
If you still have time remaining, run a similar experiment using the heap sort code written in lecture.