Premium
Optimal sampling strategies for quicksort
Author(s) -
McGeoch C. C.,
Tygar J. D.
Publication year - 1995
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240070403
Subject(s) - quicksort , computer science , sampling (signal processing) , parallel computing , sorting , algorithm , sorting algorithm , filter (signal processing) , computer vision
A well‐known improvement on the basic Quicksort algorithm is to sample from the subarray at each recursive stage and to use the sample median as the partition element. General sampling strategies , which allow sample size to vary as a function of subarray size, are analyzed here in terms of the total cost of comparisons required for sorting plus those required for median selection. Both this generalization and this cost measure are new to the analysis of Quicksort. A square‐root strategy, which takes a sample of size Φ(√ n ) for a subarray of size n , is shown to be optimal over a large class of strategies. The square‐root strategy has O(n 1,5 ) worst‐case cost. The exact optimal strategy for a standard implementation of Quicksort is found computationally for n below 3000. © 1995 John Wiley & Sons, Inc.