5 ms·

A killer adversary for quicksort (pdf)

18 points by gjm11 16y ago

gjm11 16y ago
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.
- deleted 16y ago
  [deleted]
c00p3r 16y ago
Randomized Quicksort?
- gjm11 16y ago
  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.)
jchonphoenix 16y ago
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.
- gjm11 16y ago
  > it relies on deterministically placed elements 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.
  - jchonphoenix 16y ago
    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. For more information on the adversarial method see: http://www.cs.cmu.edu/afs/cs/academic/class/15451-f10/www/ http://www.cs.cmu.edu/afs/cs/academic/class/15451-f10/www/ Recitation 09/08 explains this problem in depth.
    - 16y ago
oozcitak 16y ago
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!)). [1] http://fun2010.dia.unisa.it/ http://fun2010.dia.unisa.it/ [2] http://www.tcs.ifi.lmu.de/~gruberh/data/fun07-final.pdf http://www.tcs.ifi.lmu.de/~gruberh/data/fun07-final.pdf (pdf)

18 points by gjm11 16y ago

gjm11 16y ago

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.

deleted 16y ago
[deleted]

c00p3r 16y ago

Randomized Quicksort?

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

jchonphoenix 16y ago

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.

gjm11 16y ago
> it relies on deterministically placed elements 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.
- jchonphoenix 16y ago
  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. For more information on the adversarial method see: http://www.cs.cmu.edu/afs/cs/academic/class/15451-f10/www/ http://www.cs.cmu.edu/afs/cs/academic/class/15451-f10/www/ Recitation 09/08 explains this problem in depth.
  - 16y ago

oozcitak 16y ago

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!)). [1] http://fun2010.dia.unisa.it/ http://fun2010.dia.unisa.it/ [2] http://www.tcs.ifi.lmu.de/~gruberh/data/fun07-final.pdf http://www.tcs.ifi.lmu.de/~gruberh/data/fun07-final.pdf (pdf)