The actual runtime of applying quick-sort to an integer array heavily relies on the choice of pivots.It is well known that picking a random pivot does not work as good as taking the median of three, or the ninther of the array.Obviously, for comparison we need to fix a model of computation / cost per operation.Assume we are working in a model where each comparison between elements costs $1$, while swapping two elements costs $\gamma$ for some $\gamma>0$.If we invest more effort in finding a good pivot (e.g., take the median of $k$ random samples), we might make more comparisons, but swap less elements.Under this model, what is the optimal (in terms of expected cost) pivot choosing strategy (i.e., if our array is of size $n$, how many elements $k$ should we sample before deciding which pivot to use)?(We assume that the input might be adversarial, so taking as pivot the median of uniformly sampled elements seems like the right thing to do).
Optimal pivot selection for quick-sort
algorithms;algorithm analysis;sorting;randomized algorithms;quicksort