MA214 Algorithms and Data Structures
2023/24
Exercises 5
(Quick Sort, decision trees, Counting Sort)
Exercise 5.1. Quick Sort 4 pts
(a) Give an example showing that the implementation of the Quick Sort algorithm discussed in the lecture is not stable.
(b) Suppose you can use additional space. Explain how the Partition procedure can be modified so that Quick Sort becomes stable.
(c) Implement the proposed Partition procedure in Python.
(d) One disadvantage of the (non-randomized) Quick Sort algorithm discussed in the lecture is that it takes worst-case time Θ(n2 ), even on inputs that are already sorted. One attempt to fix this is the “median-of-three rule.” This rule looks at the first, the middle, and the last entry and takes the median of the three as a pivot. Implement this modified partition procedure in Python.
(e) What is the worst-case running time of your algorithm from (d)?
Exercise 5.2. Decision tree for Quick Sort 4 pts
Consider the variant of Quick Sort that we discussed in the lecture, in which the Parti- tion procedure picks the last element as pivot.
(a) Draw the decision tree for inputs A of length |A| = 3.
(b) Overall inputs A of length |A| = 3, what is the maximum number of comparisons Quick Sort needs to carry out to determine the output?
(c) Give an example input that achieves that maximum number.
(d) How many reachable leaves are in the decision tree for Quick Sort on inputs A of length |A| = 3?
(e) For each reachable leaf, give an example input that leads to that leaf.
Exercise 5.3. Counting Sort and Radix Sort 2 pts
(a) In the Counting Sort algorithm that we saw in the lectures, inStep 3 the elements of the list A are traversed in reversed order. Consider a variant in which the elements of A are traversed from beginning to end instead (and everything else remains the same). Show that this variant is not stable.
(b) Assume the Counting Sort variant from (a) is used in the stages of Radix Sort. Show that the resulting algorithm is not correct.