ssoelvsten / quicksort-test Goto Github PK

The current implementation always swaps pivot_elem with i_elem, but that is a waste of computations, if they are the same. We can decrease the number of swaps (and with it the running time), if we only swap, when it indeed may change the array.

There are currently only 3 unit tests in test/, which do obviously not cover all interesting cases. Furthermore, we use unit tests in this project to get as close to verifying our algorithms without using an actual proof assistant.

Add as many missing test cases that you can think of; this also includes any cases currently covered, but not satisfiably so.

Currently we hardcode the choice of pivot to be high_idx. Yet, we would like to support other strategies for picking the pivot that are better in practice. It is important to notice, that the partitioning procedure as per Lomuto requires the pivot element to reside at high_idx before starting the partition step.

The pivot strategies we want to support are:

• Pick the element at high_idx. Notice, that this is an O(N²) solution for sorted (and reversely sorted) inputs.
• A simple improvement to the above is the median of 3 pivot.
• An even better solution is to pick the pivot as the median of 1 up to 5 randomly sampled entries from the array.

We want to support all versions simultaneously, so we need to use policies to change the behaviour of the pivot derivation.

On the feature/hoare branch is an implementation of the original quicksort as by Tony Hoare. Using the policy pattern allow the user to switch between one partitioning algorithm and another.