4
$\begingroup$

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).

$\endgroup$
2
$\begingroup$

This paper [1] describes `hyper-quicksort': it uses an offline learning technique to empirically determine the value of $k$ which minimizes the power consumption of quicksort against a pathological adversary [2].

[1] Jerry Swan and Nathan Burles. “Templar - A Framework for Template-Method Hyper-Heuristics”. In: Genetic Programming - 18th European Conference, EuroGP 2015, Copenhagen, Denmark, April 8-10, 2015, Proceedings. 2015, pp. 205–216. doi: 10.1007/978-3-319-16501-1˙17.

[2] "A Killer Adversary for Quicksort", M. D. McIlroy. Software Practice and Experience, 1999.

$\endgroup$
2
$\begingroup$

The first thing to note specifically for integer arrays is that quicksort might not be the best choice for sorting depending on the possible range of values. A counting sort may be more appropriate, for example.

In the general case (i.e. not specific to integers), Martinez and Roura analyzed this problem for both quicksort and (single order statistic) quickselect. See "Optimal Sampling Strategies in Quicksort and Quickselect" SIAM Journal on Computing http://dx.doi.org/10.1137/S0097539700382108

The short answer is that the optimal strategy is to pick as the pivot element the median of a sample of elements, with the sample size roughly proportional to the square root of the number of elements in the array to be sorted, unless swapping is extraordinarily expensive. Specifically for simple types (e.g. integers), swapping is not expected to be expensive; it may be less costly than comparison via a function call, as in qsort.

That strategy also changes the worst-case (adversarial input) performance from quadratic to polynomial with an exponent of 1.5; see also McGeoch and Tygar "Optimal Sampling Strategies for Quicksort" Random Structures and Algorithms http://dx.doi.org/10.1002/rsa.3240070403

Instead of using the exact median of the samples, a lower-cost option is to approximate the median with a pseudomedian. One which can be scaled with sample size and which provides an increasingly accurate estimate of the median as sample size increases is the remedian as described by Rousseeuw and Bassett in "The Remedian: A Robust Averaging Method for Large Data Sets" Journal of the American Statistical Association http://amstat.tandfonline.com/doi/pdf/10.1080/01621459.1990.10475311 See also Battiato et al. "An Efficient Algorithm for the Approximate Median Selection Problem" in Proceedings of the 4th Italian Conference on Algorithms and Complexity http://dl.acm.org/citation.cfm?id=648257.753042 (it's the same remedian, "rediscovered" by the authors about a decade after Rousseeuw and Bassett).

For an even deeper dive (especially regarding the importance of quality of sampling as well as quantity), see https://github.com/brucelilly/quickselect/blob/master/lib/libmedian/doc/pub/generic/paper.pdf or the video at https://www.youtube.com/watch?v=iWmAf4RMMiM There you'll also find a way to get the adversarial performance to remain linearithmic (as opposed to going polynomial) without deterioration in non-adversarial input performance.

You say

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.

What typically happens (for uniformly distributed random input) is that a better (i.e. closer to the true median) pivot results in fewer overall comparisons during sorting but more swaps. With a pivot close to the median every time, the number of comparisons to sort (ignoring comparisons for pivot selection) is $N \log _ 2 N$ and the number of swaps (if efficiently arranged) is 1/4 $ N \log _ 2 N$. On the other hand, a randomly selected pivot element leads to 1.386 $N \log _ 2 N$ comparisons but only 1/6 $N \log _ 2 N$ swaps (more than 8 times as many comparisons as swaps). The two are related; a reduction in the number of swaps implies a lopsided partition (about 78.9%/21.1% for 1/6 $N \log _ 2 N$ swaps) and that leads to an overall increase in the number of comparisons because the problem size is reduced by less than half. The key to minimizing comparisons is using an efficient pseudomedian, one which provides a good estimate of the median with much fewer comparisons than the ~2N which are expected to find the exact median. The remedian with base 3 computed on a sample of size $\sqrt {N}$ costs about 1.5 $\sqrt{N}$ comparisons, which is much less than 2N for reasonable N.

$\endgroup$
  • $\begingroup$ The worst case of always picking the smallest or largest item as the pivot leads to N swaps only. If swaps are very expensive then you want a slightly non optimal pivot. $\endgroup$ – gnasher729 May 18 '18 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.