Worst-case performance of quickSort / getPivot
Ivan Kazmenko
gassa at mail.ru
Sun Nov 17 02:20:59 PST 2013
On Sunday, 17 November 2013 at 03:58:58 UTC, Andrei Alexandrescu
wrote:
> On 11/16/13 5:07 PM, Ivan Kazmenko wrote:
>> The above is just my retelling of a great short article "A
>> Killer
>> Adversary for Quicksort" by M. D. McIlroy here:
>> http://www.cs.dartmouth.edu/~doug/mdmspe.pdf
>
> Nice story, but the setup is a tad tenuous (albeit indeed
> theoretically interesting). For starters, if the attacker has a
> hook into the comparison function, they could trivially do a
> lot worse...
Actually, I was thinking about a two phase attack, and it is not
at all unlikely.
0. Say, the Sorter presents a library quicksort solution. It may
be closed source, but can take comparison function as argument.
1. On the preparation phase, the Attacker uses the tricky
comparison function described previously. What's important is
that, besides observing Theta(n^2) behavior once, he now gets a
real array a[] such that this behavior can be reproduced.
2. On the attack phase, the Attacker does not need access to the
comparison function. He just feeds the array obtained on the
previous step as plain data.
Ivan Kazmenko.
More information about the Digitalmars-d
mailing list