7
$\begingroup$

Somehow I thought about quicksort last night and was reading about it on Wikipedia. The interesting part for me was: 'If we could consistently choose a pivot from the middle 50 percent, we would only have to split the list at most $\log_{4/3} n$. The choice of the pivot seems to be one possible problem of quicksort that can lead to $O(n^2)$ behavior.

My idea was: If in each step one would use the mean of the partition as pivot, this could increase the speed significantly. Especially after a few steps, when outliers are in their own division of the list, the mean and median should be very close to each other (once again, looking at large lists). The additional time during each step to calculate the mean should be $n$. Therefore:

Quicksort estimated time: $nA\log_{4/3} n$

Quicksort_mean estimated time: $2nA\log_{5/3} n$

(5/3 is most likely a conservative estimation by me, could as well be closer to 2, as subsets should quickly be without outliers). So, starting at around 10,000 entries Quicksort_mean would be (on average) faster than Quicksort. Furthermore, it would never risk to be $O(n^2)$, as it is bound to not take the minimal or maximal element of the stack.

My main question is: Did I miss anything? I have to admit, I never implemented quicksort myself, so I might miss out on other parts of the whole thing (storage, etc.)

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Did you actually solve the updated recurrence in order to get that "runtime", or did you just add another $n$? (The latter would be wrong.) $\endgroup$ – Raphael♦ Nov 28 '14 at 14:51
  • $\begingroup$ (disclaimer: it's been a long time since I've seriously looked at this stuff, and my knowledge may be outdated) Quick sort is only a factor of two faster than its main competitors which have good worst-case behavior, so doing anything to make quick sort significantly slower in the best case eliminates the reason to use it instead of other algorithms. $\endgroup$ – Hurkyl Nov 29 '14 at 2:10
  • $\begingroup$ I simply added another n. I know that it is 'wrong', but calculating the mean should be superfast (n additions, which could be done while sorting and number of partitions divisions). My knowledge about competitors is not very good (as I said, was just a completely random thought while being half asleep...) $\endgroup$ – Johannes Becker Nov 30 '14 at 11:34
10
$\begingroup$

Using the mean for your partition does not prevent the $\Omega(n^2)$ worst-case behavior. It occurs when the input list is exponentially increasing. Consider the input:

$1,n^2,n^3,\ldots,n^n$

The mean of this set is (asymptotically) $n^{n-1}$ so you obtain the worst partition possible. This is a bit of a cheat considering that storing the list takes $\Omega(n^2)$ space if the numbers are represented as integers. But if you are sorting floating-point numbers then this scenario is concievable.

However, it is possible to calculate the median of a set (or any other order statistic for that matter) in $O(n)$ time so if you really care about run time guarantees for quick sort you should use that rather than the mean.

However, in all practical scenarios the additional cost of computing the mean/median is so large that picking a random pivot almost always is faster.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ That's a mean list :D (I guess you would reach infinity pretty quickly, so you wouldn't be able to have a very high number n). My point was that O(n) is not automatically O(n). In comparison, calculating the median is A*n with A bigger than 1. In comparison, calculating the mean should be close to 1*n. So I think it could increase the run time average (was not that interested in run time guarantees). I have to admit, the whole thing was just a train of thought that didn't leave me alone tonight. So I decided to put it here in case somebody finds it interesting... $\endgroup$ – Johannes Becker Nov 28 '14 at 14:47
  • 1
    $\begingroup$ The last paragraph is very important: yes, you can optimise the recursion depth by choosing better pivots, but it comes at a cost. Rigorous analysis is necessary for determining whether it's worth it. See e.g. Sedgewick's thesis; the answer has often been "no" (intuition: you always pay for choosing better pivots but only sometimes for choosing more naively.). $\endgroup$ – Raphael♦ Nov 28 '14 at 14:54
  • $\begingroup$ Many sort criteria don't have a "mean", for example sorting a list of people by last name. $\endgroup$ – gnasher729 Apr 14 at 10:01

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.