التفاصيل البيبلوغرافية
| العنوان: |
OPTIMAL SAMPLING STRATEGIES IN QUICKSORT AND QUICKSELECT. |
| المؤلفون: |
Mart&iactue;nez, Conrado, Roura, Salvador |
| المصدر: |
SIAM Journal on Computing. 2001, Vol. 31 Issue 3, p683. 23p. |
| مصطلحات موضوعية: |
*ALGORITHMS, *STATISTICAL sampling, *STATISTICS, MEDIAN (Mathematics), SAMPLE size (Statistics) |
| مستخلص: |
It is well known that the performance of quicksort can be improved by selecting the median of a sample of elements as the pivot of each partitioning stage. For large samples the partitions are better, but the amount of additional comparisons and exchanges to find the median of the sample also increases. We show in this paper that the optimal sample size to minimize the average total cost of quicksort, as a function of the size n of the current subarray size, is a · &nradic; + o(&nradic;). We give a closed expression for a, which depends on the selection algorithm and the costs of elementary comparisons and exchanges. Moreover, we show that selecting the medians of the samples as pivots is not the best strategy when exchanges are much more expensive than comparisons. We also apply the same ideas and techniques to the analysis of quickselect and get similar results. [ABSTRACT FROM AUTHOR] |
|
Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Business Source Index |
Full Text Finder