arXiv:1507.04220cs.DS
A numerical analysis of Quicksort: How many cases are bad cases?
Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.
Abstract
We present numerical results for the probability of bad cases for Quicksort, i.e. cases of input data for which the sorting cost considerably exceeds that of the average. Dynamic programming was used to compute solutions of the recurrence for the frequency distributions of comparisons. From these solutions, probabilities of numbers of comparisons above certain thresholds relative to the average were extracted. Computations were done for array sizes up to n = 500 elements and for several methods to select the partitioning element, from a simple random selection to what we call "recursive median of three medians." We found that the probability strongly depends on the selection method: for n = 500 and a theshold 25% above the average number of comparisons it ranges from 2.2*10^(-3) to 3.0*10^(-23). A version of Quicksort based on the recursive median of medians approach is proposed, for which our data suggest a worst case time complexity of O(n^1.37).
If you're going to post articles from arxiv, please post the top-level description so I can read the abstract before being forced to download a PDF document. http://arxiv.org/abs/1507.04220
coherentponyView on HNParent context