median of three values strategy
Solution 1
The median of three has you look at the first, middle and last elements of the array, and choose the median of those three elements as the pivot.
To get the "full effect" of the median of three, it's also important to sort those three items, not just use the median as the pivot -- this doesn't affect what's chosen as the pivot in the current iteration, but can/will affect what's used as the pivot in the next recursive call, which helps to limit the bad behavior for a few initial orderings (one that turns out to be particularly bad in many cases is an array that's sorted, except for having the smallest element at the high end of the array (or largest element at the low end). For example:
Compared to picking the pivot randomly:
- It ensures that one common case (fully sorted data) remains optimal.
- It's more difficult to manipulate into giving the worst case.
- A PRNG is often relatively slow.
That second point probably bears a bit more explanation. If you used the obvious (rand()
) random number generator, it's fairly easy (for many cases, anyway) for somebody to arrange the elements so it'll continually choose poor pivots. This can be a serious concern for something like a web server that may be sorting data that's been entered by a potential attacker, who could mount a DoS attack by getting your server to waste a lot of time sorting the data. In a case like this, you could use a truly random seed, or you could include your own PRNG instead of using rand() -- or you use use Median of three, which also has the other advantages mentioned.
On the other hand, if you use a sufficiently random generator (e.g., a hardware generator or encryption in counter mode) it's probably more difficult to force a bad case than it is for a median of three selection. At the same time, achieving that level of randomness typically has quite a bit of overhead of its own, so unless you really expect to be attacked in this case, it's probably not worthwhile (and if you do, it's probably worth at least considering an alternative that guarantees O(N log N) worst case, such as a merge sort or heap sort.
Solution 2
Think faster... C example....
int medianThree(int a, int b, int c) {
if ((a > b) ^ (a > c))
return a;
else if ((b < a) ^ (b < c))
return b;
else
return c;
}
This uses bitwise XOR
operator. So you would read:
- Is
a
greater than exclusively one of the others?return a
- Is
b
smaller than exclusively one of the others?return b
- If none of above:
return c
Note that by switching the comparison for b
the method also covers all cases where some inputs are equal. Also that way we repeat the same comparison a > b
is the same as b < a
, smart compilers can reuse and optimize that.
The median approach is faster because it would lead to more evenly partitioning in array, since the partitioning is based on the pivot value.
In the worst case scenario with a random pick or a fixed pick you would partition every array into an array containing just the pivot and another array with the rest, leading to an O(n²) complexity.
Using the median approach you make sure that won't happen, but instead you are introducing an overhead for calculating the median.
EDIT:
Benchmarks results show XOR
is 32 times faster than Bigger
even though I optimized Bigger a little:
You need to recall that XOR
is actually a very basic operator of the CPU's Arithmetic Logic Unit (ALU), then although in C it may seem a bit hacky, under the hood it is compiling to the very efficient XOR
assembly operator.
Solution 3
An implementation of Median of Three I've found works well in my quick sorts.
(Python)
# Get the median of three of the array, changing the array as you do.
# arr = Data Structure (List)
# left = Left most index into list to find MOT on.
# right = Right most index into list to find MOT on
def MedianOfThree(arr, left, right):
mid = (left + right)/2
if arr[right] < arr[left]:
Swap(arr, left, right)
if arr[mid] < arr[left]:
Swap(arr, mid, left)
if arr[right] < arr[mid]:
Swap(arr, right, mid)
return mid
# Generic Swap for manipulating list data.
def Swap(arr, left, right):
temp = arr[left]
arr[left] = arr[right]
arr[right] = temp
Solution 4
The common/vanilla quicksort selects as a pivot the rightmost element. This has the consequence that it exhibits pathological performance O(N²) for a number of cases. In particular the sorted and the reverse sorted collections. In both cases the rightmost element is the worst possible element to select as a pivot. The pivot is ideally thought to me in the middle of the partitioning. The partitioning is supposed to split the data with the pivot into two sections, a low and a high section. Low section being lower than the pivot, the high section being higher.
Median-of-three pivot selection:
- select leftmost, middle and rightmost element
- order them to the left partition, pivot and right partition. Use the pivot in the same fashion as regular quicksort.
The common pathologies O(N²) of sorted / reverse sorted inputs are mitigated by this. It is still easy to create pathological inputs to median-of-three. But it is a constructed and malicious use. Not a natural ordering.
Randomized pivot:
- select a random pivot. Use this as a regular pivot element.
If random, this does not exhibit pathological O(N²) behavior. The random pivot is usually quite likely computationally intensive for a generic sort and as such undesirable. And if it's not random (i.e. srand(0); , rand(), predictable and vulnerable to the same O(N²) exploit as above.
Note that the random pivot does not benefit from selecting more than one element. Mainly because the effect of the median is already intrinsic, and a random value is more computationally intensive than the ordering of two elements.
Solution 5
Think simple... Python example....
def bigger(a,b): #Find the bigger of two numbers ... if a > b: return a else: return b def biggest(a,b,c): #Find the biggest of three numbers ... return bigger(a,bigger(b,c)) def median(a,b,c): #Just dance! x = biggest(a,b,c) if x == a: return bigger(b,c) if x == b: return bigger(a,c) else: return bigger(a,b)
Abdul Samad
Updated on September 28, 2021Comments
-
Abdul Samad over 2 years
What is the median of three strategy to select the pivot value in quick sort?
I am reading it on the web, but I couldn't figure it out what exactly it is? And also how it is better than the randomized quick sort.
-
Abdul Samad over 12 yearsHow it is better than random quick sort as we have to generate three random numbers in this case instead of one if we are choosing the numbers with random number selection method?
-
Abdul Samad over 12 yearsWell i understand your point but what about the overhead of generating the random numbers: Don't you think that in the case where we choose single random number as pivot is better than generating three random numbers.
-
Rob Neuhaus over 12 yearsIn general when you pick the pivot, picking the overall median would give you the most balanced split, and hence the best run time. However, picking the true median is time consuming. You get a better approximate median when you sample 3 numbers than when you just sample 1. In general if the approx median finding heuristic was more sophisticated, it would do more sampling for larger arrays (where the pay off is greater), and less sampling for smaller arrays.
-
Abdul Samad over 12 yearsOkay by choosing the three number you mean choosing the three random indexes of the array. Is it true? Or other wise there is a very big chance that you got out of bound exception if you choose three random values.
-
Rob Neuhaus over 12 yearsYes, I mean choosing three random indices in the array.
-
ordinary over 10 yearsHow is it fairy easy for someone to create a pathological ordering when you are using rand()? How can they predict the outcome of a PRNG?
-
Jerry Coffin over 10 years@ordinary:
rand()
is typically a linear congruential generator. One method for such generators is described on Crypto.SE. In theory, rand() could be a cryptographically secure generator, but that's rare (to say the least). -
hat_to_the_back almost 9 years@JerryCoffin can I ask why do people use the median of 3 instead of 5 ,6 or even 7?
-
Jerry Coffin almost 9 years@user2079139: the more you take the median of, the slower you sort gets, so you generally want to choose as small a number as you can and still avoid major problems.
-
Dan R almost 8 yearsI agree with the comments on using a poor PRNG, but isn't it much easier to force a worst case on meadian of 3? You just make those three numbers the largest, then the next median the next-largest, and so on.
-
Jerry Coffin almost 8 years@DanRoche: If you know exactly which three numbers they choose the median from, it's fairly easy to manipulate. If you know what PRNG they're using, that can also be trivial to manipulate. A PRNG good enough that it's hard to guess is also typically slow enough that it'll cause a substantial slow down for other cases. If you were going to do this at all, I'd do it as a fall-back when/if recursion using the normal methods gets too deep (about like introsort does when it switches to heap sort).
-
Remo.D over 7 years@JerryCoffin: shouldn't you also know the seed for the PNRG? I feel that even something as trivial as seeding a bad PNRG using the process PID or time() would make more difficult to create a pathological case for random selection than for the median selection (or any fixed strategy). Am I missing something?
-
kwrl about 7 yearsa comment to the downgrade would be nice!
-
Randy almost 7 yearsYou don't need biggest. Instead just set x equal to bigger(a, bigger(b, c))
-
ZachB over 5 yearsI didn't downvote, but I suspect this was downvoted because the question is about the median-of-three strategy as it pertains to quicksort/quickselect, not just finding the median of three elements.
-
igsm over 4 yearsOr, swapping operation can be done in one line e.g.:
arr[left], arr[right] = arr[right], arr[left]
-
Tomer Wolberg almost 4 yearsDoesn't the partition around the median pivot automatically sorts the 3 elements? So there's no reason to sort them.