3 ms·

"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

"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.

gjm11 16y ago
> 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 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.
- jchonphoenix 16y ago
  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).
  - gjm11 16y ago
    I think we're at cross purposes here. 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.
    - jchonphoenix 16y ago
      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.
      - sesqu 16y ago
        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).

gjm11 16y ago

> 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 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.

jchonphoenix 16y ago
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).
- gjm11 16y ago
  I think we're at cross purposes here. 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.
  - jchonphoenix 16y ago
    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.
    - sesqu 16y ago
      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).