4 ms·

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 th

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).
    - jchonphoenix 16y ago
      ... 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.
      - sesqu 16y ago
        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.

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).
  - jchonphoenix 16y ago
    ... 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.
    - sesqu 16y ago
      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.