2
$\begingroup$

If we employ quicksort by selecting the pivot as the median of three elements viz., the first element, the middle element and the last element, then when will the algorithm hit worst case? and also can anyone give an example including integers?

Thanks.

Note: I have searched online for quicksort's worst case, but all of them are referring to quicksort wherein the pivot is either the first element or the last element, but what I want is completely different.

$\endgroup$
  • 2
    $\begingroup$ What are your thoughts? What have you tried? Where did you get stuck? Have you tried constructing a counterexample? We want to help you understand concepts, not do your exercise for you. $\endgroup$ – D.W. Apr 23 '16 at 4:09
  • $\begingroup$ I am a student yes, but this is absolutely not part of my exercise or anything. My professor said that to overcome the worst case of O(n^2), we choose the median pivot, which led me to thinking if there was an upper cap even for this algorithm. That's all. And I have no idea how to even analyze such algorithms, hence the question. I was thinking if the pivot happened to be the largest element in the array, then maybe it's the worst case, but I am not sure if this is indeed worst case and on top of that I don't know what complexity would be in this case, hence the question. $\endgroup$ – user47605 Apr 23 '16 at 5:12
  • 1
    $\begingroup$ Try creating a counterexample. It's not as hard as you might think. Play with some small examples of input arrays, to construct examples where quicksort will be very inefficient. It will be instructive and fun. You can do it -- give it a try! Then edit the question and show us what you've tried. You suggest making the pivot the largest element; that sounds promising. Can you do that? (possibly with a slight tweak) Can you arrange that that happens on every iteration? $\endgroup$ – D.W. Apr 23 '16 at 5:25
  • $\begingroup$ I have searched online for quicksort's worst case, but did you try to think? What is the worst case picking, e.g. the first value as pivot, and why? Are equal keys allowed? When does median of three do no better than first? $\endgroup$ – greybeard Apr 23 '16 at 10:26
  • $\begingroup$ If first value or last value is selected as pivot, I know what would happen(and that's what tons of sites online talk about), but I specifically asked for median selected pivot's worst case. $\endgroup$ – user47605 Apr 24 '16 at 3:30
4
$\begingroup$

If we employ quicksort by selecting the pivot as the median of three elements viz., the first element, the middle element and the last element, then when will the algorithm hit worst case? and also can anyone give an example including integers?

The worst case is when the selected pivot reduces the problem size by the smallest possible amount, i.e. provides as lopsided a partition as is possible. For the median of three elements, that cannot be either the largest or smallest valued element (assuming distinct values), as the definition of median ensures that in median of 3, there is one larger and one smaller element than the median.

For the rather poor but all too common case of using the median of the first, middle, and last elements (with distinct valued input), that worst case occurs when the median of the three is the second-smallest or second-largest valued element (because the largest or smallest is one of the other two of those three). That can occur when an in-order sequence of elements is rotated by just one position. Here are two examples:

1 2 3 4 5 6 7 8 0 (median of 1,5,0 is 1)

8 0 1 2 3 4 5 6 7 (median of 8,3,7 is 7)

When median of first, middle, last pivot selection is combined with most commonly used partitioning methods, the result is disastrous; each partition peels off two elements (the pivot and one extreme value) and leaves another rotated sequence remaining. The combination of first, middle, last pivot selection and a partitioning method which swaps the pivot to the first (or last) array position (rather common) is worse; it also generates rotated sequences when the input is reverse-sorted (e.g. 8 7 6 5 4 3 2 1 0).

See https://github.com/brucelilly/quickselect/blob/master/lib/libmedian/doc/pub/generic/paper.pdf and/or the video at https://www.youtube.com/watch?v=iWmAf4RMMiM for details and examples of some widely-used implementations that exhibit this behavior.

When input values are not distinct, another bad case for median of first, middle, and last elements is "organ-pipe" (bitonic) input, such as

0 1 2 3 4 3 2 1 0 (median of 0,4,0 is 0)

In the case of organ-pipe input, use of first, middle, and last elements is the worst possible choice of three elements for pivot selection!

$\endgroup$
  • $\begingroup$ Brilliant example. It looks like taking median of (first, last, any random) element is vulnerable. You could take median of three random elements. Median of the three middle elements will give good results for an array that is almost sorted, in ascending or descending order, but that might have pathological cases as well. $\endgroup$ – gnasher729 May 19 '18 at 7:07
  • $\begingroup$ @gnasher729 Thanks. Random sampling for specific input and specific sampling with random input are similar (sometimes you kill the bear, sometimes the bear kills you). The important cases for fixed sampling are specific input sequences, and the best strategy appears to be uniformly-spaced samples (e.g. 1/6, 1/2, 5/6 positions) taking into account wrap-around to handle rotations of the input. Of course, an adversary can always place elements where any fixed sampling will give poor results, and limiting performance deterioration depends on the number of samples and any other countermeasures. $\endgroup$ – Bruce Lilly May 19 '18 at 17:25

Your Answer

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