Week 11. Sorting

Reading 11 Goodrich & Tamassia: Chapter 11

Problem 12.1 Implement two sorting algorithms of your choice (in a programming language also of your choice), and compare their running times on different data sets. If you work in a group, you can implement more than two algorithms to include in the comparison.

Compare your results with the algorithmic theory. Are your results consistent with the theory? What important features does it highlight for each algorithm? What does it tell you about how to choose a sorting algorithm for specific purposes?

You need to test on a handful of different datasets with sizes so that you can observe run times ranging from less than a second to more than half a minute. The exact sizes will depend on your hardware. You can choose your data sets; e.g. integers in a small or a large range, floating point numbers, etc.

Explain why you chose the algorithms you did. Did you want to learn something in particular? Did you actually learn it?

Note. If you do not know how to measure run time, check the similar problems in the first few weeks of the semester.

Problem 12.2 The textbook offers two implementations of Merge Sort, one based on an array and one based on linked lists. Consider each one and decide whether or not it is stable. Justify your answer.

Problem 12.3 Write down pseudo-code for radix sort. Try to make it simple and emphasise key points. Explain what would happen if a non-stable inner sorting algorithm is used.

Problem 12.4 Suppose we modify the deterministic version of QuickSort to use the middle element (index $n∕2$) as pivot instead of the last one. What is the running time of this algorithm if the sequence is already sorted?