0
$\begingroup$

I am hoping someone can break something down for me in a way I can digest. I am trying to understand the running time for the median of three partitioning.

  1. What is the goal of median of three partitioning? Is it to eliminate the possibility of selecting the largest / smallest element as the pivot, thus resulting in O(n^2) run time?

  2. What would the run time be of a simple median of three partitioning function? Since there are only 3 possible comparisons, and the comparison operation runs in O(1) time, wouldn't it just be 3O(1) or negligible?

Any assistance would be greatly appreciated. Thus far, I have referenced CLRS and the following three pages for assistance:

$\endgroup$
1
$\begingroup$

You should not confuse median-of-median algorithm with median-of-3 trick.

The former is $O(n{\rm log}n)$ worst-case time.

Ans. to 1. The latter is still $O(n^2)$ worst-case time but faster in practice due to the low frequency of bad patterns seen in practice. This can be seen by the fact that randomized quicksort is $O(n{\rm log}n)$ expected time.

Ans. to 2. It is $O(n)$. The comparison work is $O(1)$ since there are only $3$ elements involving. After, determine the value of the median of three, you need to partition the array around this value. This takes $O(n)$ time.

$\endgroup$
  • $\begingroup$ I'm supposed to be researching, according to my professor, median-of-three partitioning. Could you please explain the difference to me? $\endgroup$ – Jerry M. Oct 20 '18 at 1:31
  • $\begingroup$ I did not mention that all your links only present median-of-medians. So, what is the median-of-3 that you are asking in your question? $\endgroup$ – Thinh D. Nguyen Oct 20 '18 at 1:34
  • $\begingroup$ The definition I received was the following: Given an array, a[i], ..., a[j], with j − i ≥ 2, let k = b(i + j)/2c and choose as the partition element for QUICKSORT the median among a[i], a[j], a[k] (i.e., the value that would be the middle if a[i], a[j] and a[k] were sorted). This is called median-of-three partitioning $\endgroup$ – Jerry M. Oct 20 '18 at 1:36
  • $\begingroup$ Well then I don't think I understand the goal of implementing a median-of-3 partition strategy. When I read that definition and envision it in a quicksort implementation, i envision it as finding a partition that is precisely in the middle (or close) to avoid worst-case run times and secure an O(n*lgn) run time $\endgroup$ – Jerry M. Oct 20 '18 at 1:43
  • $\begingroup$ That is why I am posting here -- so someone can help me understand more thoroughly. $\endgroup$ – Jerry M. Oct 20 '18 at 1:43
1
$\begingroup$

When you implement QuickSort, if you could magically pick the median as pivot then you would get minimal number of comparisons. If you manage to pick pivots close to the median, sorting is faster.

The median of three random elements is usually closer to the median of the array than a single random element. Throw three dice repeatedly and write down the medians. You will get 3 and 4 much more often than the other numbers.

$\endgroup$

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.