Loading...
Loading...

Go to the content (press return)

Optimal sampling strategies in quicksort and quickselect

Author
Martinez, C.; Roura, S.
Type of activity
Report
Date
1998-01
Code
LSI-98-1-R
Repository
http://hdl.handle.net/2117/83994 Open in new window
Abstract
It is well-known that the performance of quicksort may substantially be improved by selecting the median of a sample of three elements as the pivot of each partitioning stage. This variant makes more unlikely the worst-case (by decreasing the probability of uneven partitions), and improves the average number of comparisons as well. It is easily generalizable to samples of size s = 2k + 1. The larger the samples, the better the partitions, but more additional comparison will be needed to find th...
Citation
Martinez, C., Roura, S. "Optimal sampling strategies in quicksort and quickselect". 1998.
Keywords
Algorithms, Divide-and-conquer, Quickselect, Quicksort
Group of research
ALBCOM - Algorithms, Computational Biology, Complexity and Formal Methods

Participants

Attachments