Problem set week 7

The idea with this problem set is that you should practice on the following thing:

• Sorting.

Exercises:

1. Implement one quadratic and one efficient sorting algorithm. Compare the run-times of these implementations and an optimised implementation from a standard library. Document your results.

   Can you think of a good way to test your implementations?

2. Out of the sorting algorithms you know, which would sort one million 32-bit integers in the least amount of time? Back up your answer/guess with a coherent argument.

3. Why is the following partitioning strategy for quicksort bad?

   • Use a median-of-three strategy to find the pivot p.

   • Partition the remaining elements R into S₁ = {x | x ∈ R, x ≤ p} and S₂ = {x | x ∈ R, x > p}.

Solutions.