4 ms·
It doesn't have to have poor worst-case behavior: https://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf https://www.cs.princeton.edu/~rs/talks/Quicksor
by maxlybbert 12y ago
It doesn't have to have poor worst-case behavior: https://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf https://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pd... (from the author of the Algorithms textbook used at my college).
- ufo 12y agoCorrect 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 ).