Worst-case performance of quickSort / getPivot

Ivan Kazmenko gassa at mail.ru
Sun Nov 17 05:14:12 PST 2013


On Sunday, 17 November 2013 at 13:07:40 UTC, Timon Gehr wrote:
> On 11/17/2013 02:07 AM, Ivan Kazmenko wrote:
>> The random pick fails in the following sense: if we seed the 
>> RNG,
>> construct a killer case, and then start with the same seed, we 
>> get
>> Theta(n^2) behavior reproduced.
>
> Hence, in no sense. This does not perform independent uniform 
> random picks.

Not at all.  There is a number of situations where you want your 
program to use RNG, but it is also important for the result to be 
reproducible.  In such cases, you typically store the RNG seed 
for re-use.

Of course there are also many cases where you don't need 
reproducibility guarantees, and there, the attack is useless.

Ivan Kazmenko.


More information about the Digitalmars-d mailing list