5
$\begingroup$

Is the jury still out on this or do we now know which of the above mentioned ways of randomizing Quick Sort is the most optimum as far as average case running time (averaged over all possible input arrays, with all permutations of the numbers being equally likely) is concerned?

Or perhaps, has a case been made for the assertion that a generalization is not possible?

Improve this question
$\endgroup$
3
  • $\begingroup$ This would be clearer if you explained what "3/'Nther'" meant. $\endgroup$
    – Rick Decker
    Commented Nov 3, 2015 at 2:15
  • $\begingroup$ @RickDecker It's a particular partitioning + pivot selection strategy, iirc. $\endgroup$
    – Raphael
    Commented Nov 3, 2015 at 6:41
  • 1
    $\begingroup$ What do you mean by "most optimal"? (For one thing, "optimal" does not have a superlative, it is one.) Which cost measure do you want to use? See also here. $\endgroup$
    – Raphael
    Commented Nov 3, 2015 at 6:43

1 Answer 1

Reset to default
4
$\begingroup$

The asymptotic expected running time of quicksort is $\Theta(n \log n)$: this is true for all three pivot methods you mention.

Wikipedia says that the expected number of comparisons is approximately $1.386 n \log n$ when using a random pivot, and approximately $1.188 n \log n$ when using median-of-three pivot. There's some experimental evidence that the number of comparisons might be about $1.094n \log n$ when using a ninther pivot for large arrays, median-of-three for medium-sized arrays, and single element for small arrays. See the following research paper:

Jon L. Bentley, M. Douglas McIlroy, "Engineering a Sort Function". Software Practice and Experience, 23(11):1249-1265, Nov 1993.

(This paper is cited in the Wikipedia article I mentioned above.)

I'm not familiar with the "uniform shuffle" pivot selection method. It sounds equivalent to choosing a random element and using that as the pivot.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Sedgewick proposes that we uniformly shuffle the entire input array once, at start of the sorting and then just pick the first element every time in each recursive call to the partition method. I have updated the post's title to make it a little more helpful. $\endgroup$
    – balajeerc
    Commented Nov 3, 2015 at 1:05
  • $\begingroup$ Why the expected depth is $O(\log N)$? $\endgroup$
    – Sergey Zaitsev
    Commented Oct 7, 2017 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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