This is by no means new, but it's not terribly well known and I think it's both beautiful and hilarious.
Almost all quicksort implementations take quadratic time in the worst case. They generally do a rather good job of avoiding that worst case, by careful choice of pivots[1]. McIlroy has a very simple technique for making that choice produce bad results in almost all quicksort implementations.
Unfortunately, he has to cheat a bit. His code doesn't construct an array full of evil values. Rather, he has an adaptive comparison function that, in effect, constructs the array of evil during the sorting process. (But it always behaves consistently; the elements of the array are, so to speak, undecided until the sorting routine looks at them, but they don't change after they've been looked at.)
[1] For those who don't know, here's the quicksort algorithm: Choose one element of your array (the "pivot"); partition the array into things smaller than the pivot and things larger than the pivot; then, recursively, sort the two parts you just made. This works well, at least when you aren't facing McIlroy's evil adversary, because (1) you can do the partitioning operation very efficiently and (2) if you're not very unlucky with your choice of pivot you usually succeed in dividing the array into two parts of roughly equal size. But if the pivot is, say, always the smallest element of your array, you'll get terrible results.
In typical cases the "killer adversary" will still be able to make a good guess at when the pivot is being found, and drive the quicksort routine into bad behaviour, even when the pivot selection is randomized. (Of course that means that the resulting array will typically not produce bad behaviour if it's sorted with the RNG in a different initial state, whereas for nonrandomized quicksorts the adversary produces an array that will reliably provoke quadratic-time behaviour.)
If you randomize the values, the expected running time of your algorithm will be O(nlogn). Worst case is still O(n^2). Additionally, the adversarial argument presented is voided because it relies on deterministically placed elements, which allows the adversary to actually choose them on the fly.
In general, a randomized algorithm is better than its deterministic counterpart.
Citation: I'm a 15-451 (Algorithm Design and Analysis) TA at Carnegie Mellon and I just gave this lecture in recitation.
Did you read the paper? If you provide McIlroy's adversarial comparison function to a (no matter how genuinely) randomized quicksort algorithm, then typically it will provoke quadratic-time behaviour, and the final state of the array will be such that passing it into the quicksort function would have produced that same quadratic-time behaviour, given the same random choices.
(See the paragraph beginning "The adversarial method works for almost any polymorphic program recognizable as quicksort".)
What the adversary can't do, of course, is to produce an array that on a subsequent run, with different random choices, will again provoke bad behaviour. The average case of quicksort is O(n log n), and nothing McIlroy's adversary can do will change that.
No, actually it does rely on deterministically placed elements. And its analyzing unix qsort which is a deterministic algorithm.
Unless I'm misunderstanding the paper (which I could be).
The argument relies on the fact that the adversary can choose the elements on the fly. This requires the input be deterministic so that the adversary knows what elements are where. If you randomize the input, the adversary will have no knowledge of the input and thus is not able to choose which elements go in which index. This would be randomly generated.
"An adversary can make such a quicksort go quadratic by arranging for the pivot to compare low against almost all items not seen during pivot selection, so the partition will be lopsided. Those items may be regarded as a “gas” of values whose relationship to each other is unknown. The exact values don’t matter as long as they are not compared against each other. Quadratic behavior is guaranteed since n − O(1) gas values must survive pivot selection among n items. Almost all partition high."
This paragraph from the paper is a false statement when applied to randomized quicksort. The adversary cannot "arrange for the pivot to compare low against all items not seen during pivot selection," if quicksort was randomized namely because the adversary has no information about the other elements. In deterministic quicksort he does. Thus, this is where his argument breaks down in relation to randomized quicksort.
I think he focused on deterministic and just tacked on the statement about randomized without thinking about it. Its a very subtle error to make when using the adversarial method against a randomized algorithm and because his analysis deals with deterministic quicksort I doubt he put much thought into the randomized case.
> This paragraph from the paper is a false statement when applied to randomized quicksort.
Looks OK to me subject to the criteria McIlroy gives for the success of his method. (You did read the whole paper, not just that paragraph, right?) His adversary effectively incorporates a heuristic for telling when the pivot is being selected!
See http://pastebin.com/5B5qffJt for a simple demonstration of McIlroy's adversary in action against a randomized quicksort implementation. If you run the code there, you'll find that the "good" case (without the McIlroy adversary) typically takes about 1.5 n log n comparisons, and the "evil" case (with the McIlroy adversary) typically takes about 0.5 n^2 comparisons.
The issue isn't with the code. What I'm saying is that the code you produced is effectively a counterargument to deterministic quicksort and doesn't apply in the random case. What McIlroy is doing is selecting an element on the fly during the algorithm. If quicksort was randomized, he would not be able to do so. Thus his argument breaks down there.
If you are constructing a "worst case" for randomized quicksort, the answer is still obviously O(n^2), but the purpose of randomized quicksort is that it is O(nlogn) EXPECTED running time. Thus, by constructing a worst case input, you really haven't broken randomized quicksort at all. In fact, you're doing exactly what its intended to do: perform badly sometimes, perform well other times, and in the expected case, perform O(nlogn).
I read the entire paper, and I'm, of course, no expert, but I've ran my argument past a professor in algorithms (who is a Turing award winner), and he also believes that McIlroy's argument does not work for the randomized case.
His heuristic cannot be legitimately applied in the randomized case because the adversary simply is not allowed to choose elements in the randomized case. That, of course, is the purpose of randomization. Thus, it doesn't matter what his code or heuristic shows. His argument has a logical fallacy and thus is illegitimate (only when applied to the randomized case of course).
1. McIlroy does not claim to have an algorithm that generates (ahead of time) arrays that make a randomized quicksort take quadratic time. (Of course not; there's no such thing, and he knows that every bit as well as you or I.)
2. McIlroy does claim to have an algorithm that you can feed into a randomized quicksort with the result that it takes quadratic time -- generating the array as it goes -- provided the quicksort implementation satisfies the conditions he lists.
3. The statement you quoted from McIlroy's paper is not false. It just isn't saying what you think it's saying. When McIlroy says "an adversary" he means something like the comparator function he describes, not something that looks at the quicksort algorithm (minus whatever information is needed to determine the state of any random number generators it uses) and generates difficult data for it to handle. For the latter, the theorem you're talking about applies. For the former, it doesn't. He's not claiming to have a counterexample to the famous theorem, he's claiming to have a way of making almost any quicksort implementation (randomized or not) misbehave if you're allowed a comparison function that makes decisions on the fly. Which, in fact, he does.
The reason I posted the code was simply to demonstrate that when McIlroy says "an adversary can do X", he's telling the truth (with the notion of "adversary" he's using) and has in fact provided an adversary that does do X.
1. I don't think you understand my point (or possibly the adversarial method).
2. Unless you generate an array ahead of time, you haven't broken randomized quicksort.
3. For an adversary to have the ability to generate elements on the fly, he must have knowledge of the array, which requires the array to be generated deterministically.
4. The purpose of a randomized algorithm is to prevent the adversary from choosing elements on the fly and forcing the worst case every time.
Putting these all together, for McIlroy's adversary to have broken randomized quicksort would be claiming that randomization is useless. We all know this is false.
Stop thinking about arrays. Think ordered relations. Think collections and comparators. The sort is vulnerable to an attack at the highest abstraction level, where only necessary conditions are used. The usual implementation, using arrays of integers, is not similarly vulnerable.
I'm not a fan of randomized algorithms, incidentally. It's selling your best case upriver to ward off offensive poisoning, and adds a multiplier to running time. Still, if you're offline, memory-restricted, timesharing and public-facing, I guess randomized quicksort's better than most alternatives. I'd still be looking at median-of-medians, but that's a fair bit of extra work (so much so that it isn't really even quicksort anymore).
... Why does nobody understand how the adversarial method works? What I'm basically saying is that the usage of the comparator to create elements on the fly IS NOT LEGAL if you are trying to break randomized quicksort because this requires the adversary to have PRIOR KNOWLEDGE of the elements. He doesn't if its randomized.
First of all, we're not trying to break a proof of anything. There's a demonstrated attack on comparator-based sorts. Whether you want to allow the scenario doesn't much change the fact that that scenario is vulnerable.
Second, this method does not require prior knowledge of the elements. In fact, it disallows a large amount of information (the ordering). What prior knowledge are you claiming the adversary doesn't have but requires? He provides the set, so he has full knowledge of the members of the set (though the sorter doesn't, so this is useless knowledge). It's an unordered set with a full ordering relation, so a random permutation on initial indices will have no effect. He is the comparator, and thus has full knowledge of that as well. There is nothing else to know.
Now, you might object to the fact that the comparator is not a deterministic automaton, which is the assumption exploited, and I wish you good luck in enforcing that in your sorting routines.
Sigh. I give up. I'll just suggest you open up a copy of clrs and read the section on randomized quick sort. There is a section dealing with this killer adversary exactly and why this adversary does not kill randomized quick sort.
Your logic is failing because your thinking of this from a programmers perspective when, in reality this is an algorithm analysis problem which is theory.
I don't have that book, so you'll have to explain the reasoning if you want to convince me. I did find the MIT OCW lecture transcript on randomized quicksort, based on the book, and it described how randomization probably defeats an adversary supplying a worst-case initial permutation when the pivoting algorithm is known. That's a different adversary to the one we are discussing, even if relaxed; it has to supply an input that is consistent and fixed. They also motivated the scenario in terms of competition, which I find less reasonable than actual malevolence, but that bears little relevance now.
When theory and practise diverge, there is strong reason to hold the practise as more defensible than the theory. How would you say the practice should be amended to not suffer from this problem that is apparently not extant in theory? I hold that it cannot, for this adversary is more capable than the other.
McIlroy is not claiming to have done what you call "breaking randomized quicksort". Therefore the fact that he hasn't done that doesn't mean that he made a mistake or said anything untrue. That is all.
This needs to be presented at Fun With Algorithms [1]. Also somewhat related is the bogosort algorithm [2] which was designed to be awfully slow (average case performance O(n * n!)).
21 comments
[ 2.8 ms ] story [ 50.9 ms ] threadAlmost all quicksort implementations take quadratic time in the worst case. They generally do a rather good job of avoiding that worst case, by careful choice of pivots[1]. McIlroy has a very simple technique for making that choice produce bad results in almost all quicksort implementations.
Unfortunately, he has to cheat a bit. His code doesn't construct an array full of evil values. Rather, he has an adaptive comparison function that, in effect, constructs the array of evil during the sorting process. (But it always behaves consistently; the elements of the array are, so to speak, undecided until the sorting routine looks at them, but they don't change after they've been looked at.)
[1] For those who don't know, here's the quicksort algorithm: Choose one element of your array (the "pivot"); partition the array into things smaller than the pivot and things larger than the pivot; then, recursively, sort the two parts you just made. This works well, at least when you aren't facing McIlroy's evil adversary, because (1) you can do the partitioning operation very efficiently and (2) if you're not very unlucky with your choice of pivot you usually succeed in dividing the array into two parts of roughly equal size. But if the pivot is, say, always the smallest element of your array, you'll get terrible results.
In general, a randomized algorithm is better than its deterministic counterpart.
Citation: I'm a 15-451 (Algorithm Design and Analysis) TA at Carnegie Mellon and I just gave this lecture in recitation.
Did you read the paper? If you provide McIlroy's adversarial comparison function to a (no matter how genuinely) randomized quicksort algorithm, then typically it will provoke quadratic-time behaviour, and the final state of the array will be such that passing it into the quicksort function would have produced that same quadratic-time behaviour, given the same random choices.
(See the paragraph beginning "The adversarial method works for almost any polymorphic program recognizable as quicksort".)
What the adversary can't do, of course, is to produce an array that on a subsequent run, with different random choices, will again provoke bad behaviour. The average case of quicksort is O(n log n), and nothing McIlroy's adversary can do will change that.
Unless I'm misunderstanding the paper (which I could be).
The argument relies on the fact that the adversary can choose the elements on the fly. This requires the input be deterministic so that the adversary knows what elements are where. If you randomize the input, the adversary will have no knowledge of the input and thus is not able to choose which elements go in which index. This would be randomly generated.
For more information on the adversarial method see: http://www.cs.cmu.edu/afs/cs/academic/class/15451-f10/www/
Recitation 09/08 explains this problem in depth.
This paragraph from the paper is a false statement when applied to randomized quicksort. The adversary cannot "arrange for the pivot to compare low against all items not seen during pivot selection," if quicksort was randomized namely because the adversary has no information about the other elements. In deterministic quicksort he does. Thus, this is where his argument breaks down in relation to randomized quicksort.
I think he focused on deterministic and just tacked on the statement about randomized without thinking about it. Its a very subtle error to make when using the adversarial method against a randomized algorithm and because his analysis deals with deterministic quicksort I doubt he put much thought into the randomized case.
Looks OK to me subject to the criteria McIlroy gives for the success of his method. (You did read the whole paper, not just that paragraph, right?) His adversary effectively incorporates a heuristic for telling when the pivot is being selected!
See http://pastebin.com/5B5qffJt for a simple demonstration of McIlroy's adversary in action against a randomized quicksort implementation. If you run the code there, you'll find that the "good" case (without the McIlroy adversary) typically takes about 1.5 n log n comparisons, and the "evil" case (with the McIlroy adversary) typically takes about 0.5 n^2 comparisons.
If you are constructing a "worst case" for randomized quicksort, the answer is still obviously O(n^2), but the purpose of randomized quicksort is that it is O(nlogn) EXPECTED running time. Thus, by constructing a worst case input, you really haven't broken randomized quicksort at all. In fact, you're doing exactly what its intended to do: perform badly sometimes, perform well other times, and in the expected case, perform O(nlogn).
I read the entire paper, and I'm, of course, no expert, but I've ran my argument past a professor in algorithms (who is a Turing award winner), and he also believes that McIlroy's argument does not work for the randomized case.
His heuristic cannot be legitimately applied in the randomized case because the adversary simply is not allowed to choose elements in the randomized case. That, of course, is the purpose of randomization. Thus, it doesn't matter what his code or heuristic shows. His argument has a logical fallacy and thus is illegitimate (only when applied to the randomized case of course).
1. McIlroy does not claim to have an algorithm that generates (ahead of time) arrays that make a randomized quicksort take quadratic time. (Of course not; there's no such thing, and he knows that every bit as well as you or I.)
2. McIlroy does claim to have an algorithm that you can feed into a randomized quicksort with the result that it takes quadratic time -- generating the array as it goes -- provided the quicksort implementation satisfies the conditions he lists.
3. The statement you quoted from McIlroy's paper is not false. It just isn't saying what you think it's saying. When McIlroy says "an adversary" he means something like the comparator function he describes, not something that looks at the quicksort algorithm (minus whatever information is needed to determine the state of any random number generators it uses) and generates difficult data for it to handle. For the latter, the theorem you're talking about applies. For the former, it doesn't. He's not claiming to have a counterexample to the famous theorem, he's claiming to have a way of making almost any quicksort implementation (randomized or not) misbehave if you're allowed a comparison function that makes decisions on the fly. Which, in fact, he does.
The reason I posted the code was simply to demonstrate that when McIlroy says "an adversary can do X", he's telling the truth (with the notion of "adversary" he's using) and has in fact provided an adversary that does do X.
2. Unless you generate an array ahead of time, you haven't broken randomized quicksort.
3. For an adversary to have the ability to generate elements on the fly, he must have knowledge of the array, which requires the array to be generated deterministically.
4. The purpose of a randomized algorithm is to prevent the adversary from choosing elements on the fly and forcing the worst case every time.
Putting these all together, for McIlroy's adversary to have broken randomized quicksort would be claiming that randomization is useless. We all know this is false.
I'm not a fan of randomized algorithms, incidentally. It's selling your best case upriver to ward off offensive poisoning, and adds a multiplier to running time. Still, if you're offline, memory-restricted, timesharing and public-facing, I guess randomized quicksort's better than most alternatives. I'd still be looking at median-of-medians, but that's a fair bit of extra work (so much so that it isn't really even quicksort anymore).
Second, this method does not require prior knowledge of the elements. In fact, it disallows a large amount of information (the ordering). What prior knowledge are you claiming the adversary doesn't have but requires? He provides the set, so he has full knowledge of the members of the set (though the sorter doesn't, so this is useless knowledge). It's an unordered set with a full ordering relation, so a random permutation on initial indices will have no effect. He is the comparator, and thus has full knowledge of that as well. There is nothing else to know.
Now, you might object to the fact that the comparator is not a deterministic automaton, which is the assumption exploited, and I wish you good luck in enforcing that in your sorting routines.
Your logic is failing because your thinking of this from a programmers perspective when, in reality this is an algorithm analysis problem which is theory.
When theory and practise diverge, there is strong reason to hold the practise as more defensible than the theory. How would you say the practice should be amended to not suffer from this problem that is apparently not extant in theory? I hold that it cannot, for this adversary is more capable than the other.
[1] http://fun2010.dia.unisa.it/
[2] http://www.tcs.ifi.lmu.de/~gruberh/data/fun07-final.pdf (pdf)