3 ms·
Correct me if I'm wrong but I got the impression that prof Sedgewick's slides were about quicksort behaviour when the input has many equal keys. That would stil
by ufo 12y ago
Correct me if I'm wrong but I got the impression that prof Sedgewick's slides were about quicksort behaviour when the input has many equal keys. That would still result in quadratic runtime against maliciously crafted input.
- maxlybbert 12y agoI may have oversold Sedgewick's claim: he doesn't actually say that a properly implemented quicksort will never go quadradic; only that "The average number of compares per element ... is always within a constant factor of the entropy" and "No comparison-based algorithm can do better" (page 16). I've never looked into whether a Sedgewick-approved Quicksort can avoid worst case behavior against antiquicksort ( http://www.cs.dartmouth.edu/~doug/aqsort.c http://www.cs.dartmouth.edu/~doug/aqsort.c , http://www.cs.dartmouth.edu/~doug/mdmspe.pdf http://www.cs.dartmouth.edu/~doug/mdmspe.pdf ).